§ Center of a tree

• The remoteness / eccentricity of a vertex $v$ is its distance from its furthest node. $r(v) \equiv \max_{w \in V} d(v, w)$.
• The center of a tree is the vertex with minimum remoteness.

§ Claim: center is on any diameter.

• Let $D$ be the diameter of length $L$.
• Let $c$ be the center. We claim that $c$ lies on $D$. If so, we are done.
• If not, then there is a path from $c$ to some vertex $v$ in $D$. Let WLOG the endpoints of the diameter be $s$ and $e$, and such that $v$ is further from $s$ than $e$. That is: $d(s, v) \geq s(v, e)$. In a picture:

s----------v---e
           |
           n
           |
         n-c--n
           |
           n

• Key idea: the important distance is the distance from $v$ to $s$. So we can forget everything in a radius of $d(v, e)$, as the distance $d(v, e) < d(v, s)$, and $d(c, e) < d(c, s)$. But if we forget the structure around $v$ in a radius of $e$, all we are left with is:

s-------------------v
                    |
                    |
                    c

where clearly $v$ is closer to $s$ than to $c$, and thus $c$ 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)$, which is all that matters.

• For any node $n$ in the subtree hanging from $v$, we have $d(n, v) \leq d(v, e)$, since otherwise the path $s-v-n$ would become a path longer than the diameter, contradicting the maximality of the diameter.
• Hence, we have $d(n, v) \leq d(v, e) \leq d(v, s)$, where the second inequality comes from the assumption of $s$ and $e$. So $s$ is the node that is furthest from $v$ amongst all nodes in the graph.
• But now notice that $d(c, s) = d(c, v) + d(v, s)$, and this is the longest distance from $c$ to any other node. This implies that $d(c, s) > d(v, s)$ as $d(c, v) > 0$.
• This contradicts the minimality of the eccentricity of $c$: the longest distance from $c$ 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.