## § 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.