§ Diameter of a tree

§ Key property of the diameter

  • 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 vv. Then perform DFS again starting from this vertex vv. The farthest vertex from vv, say ww gives us the diameter (the distance from vv to ww)

§ Proof by intuition/picture:

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