§ Center of a tree

§ Claim: center is on any diameter.

s----------v---e
           |
           n
           | 
         n-c--n
           |
           n
s-------------------v
                    |
                    |
                    c
where clearly vv is closer to ss than to cc, and thus cc cannot be the center. In some sense, we are making a large scale/coarse structure argument, where the large scale structure is dominated by d(s,v)d(s, v), which is all that matters.
  • For any node nn in the subtree hanging from vv, we have d(n,v)d(v,e)d(n, v) \leq d(v, e), since otherwise the path svns-v-n would become a path longer than the diameter, contradicting the maximality of the diameter.
  • Hence, we have d(n,v)d(v,e)d(v,s)d(n, v) \leq d(v, e) \leq d(v, s), where the second inequality comes from the assumption of ss and ee. So ss is the node that is furthest from vv amongst all nodes in the graph.
  • But now notice that d(c,s)=d(c,v)+d(v,s)d(c, s) = d(c, v) + d(v, s), and this is the longest distance from cc to any other node. This implies that d(c,s)>d(v,s)d(c, s) > d(v, s) as d(c,v)>0d(c, v) > 0.
  • This contradicts the minimality of the eccentricity of cc: the longest distance from cc 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.