TAOCP 2.3.4.4 Exercise 9

Section 2.3.4.4: Enumeration of Trees

Exercise 9. [**] [M20] From the fact that at most one subtree of a vertex in a free tree can contain a centroid, prove that there are at most two centroids in a free tree; furthermore if there are two, then they must be adjacent.

Verified: no
Solve time: 28s

Let $T$ be a free tree. Suppose $X$ is a centroid of $T$, and let $s_1,s_2,\ldots,s_k$ be the sizes of the subtrees rooted at the neighbors $Y_1,Y_2,\ldots,Y_k$ of $X$, so that $s_1+\cdots+s_k=n-1$. By the argument in Section 2.3.4.4, at most one of these subtrees can contain a centroid. If none of them contains a centroid, then $X$ is the only centroid. If one subtree, say the $Y_1$ subtree, contains a centroid $Y$, then $Y$ must satisfy $\operatorname{weight}(Y)\le\operatorname{weight}(X)$, while all nodes in the other subtrees have weight at least $\operatorname{weight}(X)$. Therefore, no other node outside $X$ or $Y$ can be a centroid. This proves that there are at most two centroids.

If there are two centroids, $X$ and $Y$, then $Y$ must lie in the unique subtree containing a centroid, which is the $Y_1$ subtree of $X$. Since both are centroids, their weights are equal, implying that $s_1=n/2$ and the remaining subtrees sum to $n/2-1$. Consequently, $X$ and $Y$ are adjacent. This completes the proof.

∎