§ Center of a tree
- The remoteness / eccentricity of a vertex is its distance from its furthest node. .
- The center of a tree is the vertex with minimum remoteness.
§ Claim: center is on any diameter.
- Let be the diameter of length .
- Let be the center. We claim that lies on . If so, we are done.
- If not, then there is a path from to some vertex in . Let WLOG the endpoints of the diameter be and , and such that is further from than . That is: . In a picture:
- Key idea: the important distance is the distance from to . So we can forget everything in a radius of , as the distance , and . But if we forget the structure around in a radius of , all we are left with is:
where clearly is closer to than to , and thus cannot be the center. In some sense, we are making a large scale/coarse structure argument,
where the large scale structure is dominated by , which is all that matters.
- For any node in the subtree hanging from , we have , since otherwise the path would become a path longer than the diameter, contradicting the maximality of the diameter.
- Hence, we have , where the second inequality comes from the assumption of and . So is the node that is furthest from amongst all nodes in the graph.
- But now notice that , and this is the longest distance from to any other node. This implies that as .
- This contradicts the minimality of the eccentricity of : the longest distance from to
§ Claim: center is median of any diameter
We've already seen that center is on the diameter. Now if a center node is not on the median,
the distance to the furthest node (start/end) can be improved by moving the center node
closer to the median. So the best choice is to have the center be at (one of the) medians.
§ Claim: center does not change by removing all leaf vertices
We've shown that the center is the median of all diameters. Removing all leaves
removes two elements at the beginning and end of all diameters, leaving the
median (the center) invariant.