A formal proof is given in "On computing a longest path in a tree" by R. W. Bulterman et al.

This isn't a formal proof, but here's some insights that might help build your intuition for why it is true.

When you choose your random node s, imagine rooting the tree at s. The first thing to note is that the two endpoints of the diameter will always be leaves (or s, if s only has one child. Even in this case, the other endpoint will always be leaf).

Then, we can show that the farthest leaf u from s is one of the endpoints of the diameter. You can do this through contradiction, and I believe the main idea is something along the lines of "pretend the two endpoints are both not u. Then you can find a longer path by changing one of the endpoints to u."

Great, now this farthest node u from s is one of the endpoints of the diameter! From here it's easy, the farthest node v from u must be the other endpoint of the diameter.

Why do you need a proof? I just believe in it

Although it's not really necessary in this case, I think this might become clearer if you think instead about the centroid(s). Here's how it works:

Certainly the tree has a diameter, i.e. a longest path. Suppose the path from x to y is longest. Now consider the midpoint C of this path. (This is the centroid of the tree, more or less.) If D = d(x, y) is even, C is a vertex; otherwise it is the midpoint of an edge. (If you like, imagine making the tree bigger by adding a vertex at the midpoint of every edge; this doesn't change your problem, and now C is certainly a vertex.) Either way, d(x, C) = d(y, C) = D / 2.

Claim 1: For any vertex z, d(z, C) ≤ D / 2. Proof: Consider the paths from x to z, and then from z to y. Concatenating them, we get a (possibly degenerate) path from x to y. Since paths are essentially unique in a tree, this concatenation must pass through C, i.e. one of the paths passes through C. Thus suppose the path from x to z passes through C. Now D ≥ d(z, x) = d(z, C) + d(C, x) = d(z, C) + D / 2, which rearranges to d(z, C) ≤ D / 2.

Claim 2: For any vertex s, and a vertex u farthest from s, d(u, C) = D / 2. Proof: Have d(s, u) ≥ max(d(s, x), d(s, y)) ≥ d(s, C) + D / 2, where the second inequality comes from the previous proof. By triangle inequality, d(s, C) + d(u, C) ≥ d(s, u), so d(u, C) ≥ D / 2. By Claim 1, we are done.

Finally, by our observation above, max(d(u, x), d(u, y)) ≥ d(u, C) + D / 2 = D, and we're done.

Hopefully this tells you some more about what's going on: given any vertex s, the vertices farthest from s are precisely those which (a) have maximal distance to the centroid, and (b) don't lie on the same side of the centroid as s. In particular, the maximal distance from s is d(s, C) + D / 2.

I give a proof in this video (use the timestamps in the description to jump to the proof): https://www.youtube.com/watch?v=2PFl93WM_ao

It has pictures to go with the equations so is hopefully a bit easier to understand.

This proof is very memorable to me as I spent quite some time visualizing and proving it successfully myself.

My idea is very similar to Kognition's but I feel that the proof becomes intuitive if you visualize the diameter to be present beforehand and you are starting from a random node.

Bear my bad drawing skills

The claim of the theorem is that, if you start dfs from a random node u which is not one of the endpoints of the diameter, the farthest node v from u is one of the endpoints of the diameter.

Naming

• u — staring node

• v — farthest node from u

• d, d' — 2 endpoints of the diameter

• w — The first node in the diameter which is reached from u

What if v ≠ d, d' then either

1. From u we reach w but from there we reach a node v' ≠ v. This implies that we get a larger diameter, hence a contradiction.
2. Suppose we don't reach w, then

This shows that we can have a larger diameter, hence a contradiction. Hence we will always reach w

Do let me know if some parts of the proof is shaky. I solved this UVa problem using this idea.

Maybe..this helps