Graph Theory37 sections · 1633 units
Open in Course

Why Two-BFS Works

Intuition behind the proof

Say the true diameter is the path from xx to yy. When you BFS from a random node ss, you will reach some farthest node uu.

If uu is not on the diameter path, then there is a longer path from ss through the diameter to one of its endpoints. Contradiction: uu would not be farthest.

So uu must be on or reachable-to an endpoint of the diameter. When you BFS from uu, you will reach the other endpoint, giving you the full diameter.

This is not a full formal proof, but it is the core intuition.