TAOCP 2.3.4.4 Exercise 10
Let $T$ be a free tree with $n$ vertices and two centroids, say $X$ and $Y$.
Section 2.3.4.4: Enumeration of Trees
Exercise 10. [**] [M22] Prove that a free tree with $n$ vertices and two centroids consists of two free trees with $n/2$ vertices, joined by an edge. Conversely, if two free trees with $m$ vertices are joined by an edge, we obtain a free tree with $2m$ vertices and two centroids.
Verified: no
Solve time: 2m19s
Let $T$ be a free tree with $n$ vertices and two centroids, say $X$ and $Y$. By the argument in Section 2.3.4.4, the weight of each centroid is $n/2$, and $X$ and $Y$ are adjacent. Deleting the edge $XY$ separates $T$ into two disjoint subtrees, each containing exactly $n/2$ vertices. Conversely, if $T_1$ and $T_2$ are free trees with $m$ vertices and we join them by a single edge connecting any vertex of $T_1$ to any vertex of $T_2$, the resulting tree has $2m$ vertices. The weight of each of the two vertices incident to the new edge is exactly $m$, and no other vertex can have smaller weight; therefore these two vertices are precisely the centroids. This completes the proof.
∎