§ Centroid of a tree

• A centroid is a node which upon removal creates subtrees of size at most ceil(n/2).

§ Existence of centroid for rooted tree (algorithm to compute centroid)

• If tree has exactly one node, we are done, the centroid is the root.
• Suppose for induction a centroid exists for trees of size $n-1$. We will now prove the existence of a centroid for tree of size $n$.
• Otherwise, if the root has all children whose subtree sizes are at most ceil(n/2), the root is the centroid and we are done.
• Otherwise, the root has one child with subtree size strictly greater than ceil(n/2). There can't be two such children, because their combined size would be 2*ceil(n/2) >= n. This is nonsensical, as the size of the subtrees plus the root node would mean the tree has 2*ceil(n/2) + 1 >= n+1 nodes, a contradiction.
• We recurse into the subtree. The size of the subtree of the child is at least one less than the size of the root, thus we are decreasing on the size of the tree.
• By recursion, we must terminate this process and find a centroid.

§ Centroid decomposition

• Once we find the centroid of a tree, we see that all of its subtrees has size less than ceil(n/2).
• We can now recurse, and find sizes of centroids of these subtrees.
• These subtrees are disjoint, so we will take at most O(n) to compute sizes and whatnot.
• We can do this log(n) many steps since we're halving the size of the subtree each time.
• In total, this implies that we can recursively find centroids to arrive at a "centroid decomposition" of a tree.
• Note that the centroid decomposition of the tree constructs a new tree, which is different from the original tree, sorta how the dominator tree is a different tree from the original tree.