Problem
COM-B2-M04-P017 Two Farthest Vertices of a Tree
#17
★★★★☆ Level 4 of 5
In a tree, two vertices \(A\) and \(B\) are chosen so that the distance between them is as large as possible. Prove that both vertices are leaves.
If \(A\) has a neighbour outside the path from \(A\) to \(B\), the distance can be increased.
Consider the unique path from \(A\) to \(B\). If the degree of \(A\) is greater than \(1\), then \(A\) has a neighbour \(C\) different from the next vertex on the path to \(B\).
In a tree, the path from \(C\) to \(B\) passes through \(A\), so the distance \(CB\) is one greater than \(AB\). This contradicts the maximal choice of \(A,B\). Hence the degree of \(A\) is \(1\). Similarly, the degree of \(B\) is \(1\).
Useful preparation for the diameter of a tree.