## § Diameter of a tree

### § Key property of the diameter

• Let $p$ be a path of maximum diameter, which starts at $p$ and ends at $q$. Consider a tree where the diameter is shown in golden: • We claim that a node at distance $d$ from the left can have a subtree of height at most $d$: • Suppose this were not the case. Then, we can build a longer diameter (in pink) that is longer than the "supposed diameter" (in gold): ### § Algorithm to find the diameter:

First perform DFS to find a vertex "on the edge", say $v$. Then perform DFS again starting from this vertex $v$. The farthest vertex from $v$, say $w$ gives us the diameter (the distance from $v$ to $w$)

#### § Proof by intuition/picture:

• first imagine the tree lying flat on the table. • Hold the tree up at node $c$. It's going to fall by gravity and arrange as shown below. This is the same as performing a DFS. • Pick one of the lowest nodes (we pick $g$). Now hold the entire tree from this lowest node, and once again allow gravity to act. • This will give us new lowest nodes such as $b$. This node $b$ is going to be diameter, "because" it's the distance from a lowest node to another lowest node.