Centroids and Component Sizes

Centroids Balance Component Sizes

A tree can be viewed as a branching structure, and deleting a vertex separates that structure into pieces. A centroid is a vertex for which none of those pieces contains more than half the tree. This definition measures balance by the number of vertices on each side, not by how far vertices are from the candidate.

Throughout, a tree is a finite, nonempty, connected, simple graph with no cycles. Its order is \(n=|V|\). A component is a maximal connected subgraph. In a tree there is a unique path between each pair of vertices: connectedness gives a path, and two different paths between the same pair would contain a cycle. Deleting a vertex \(v\) means removing \(v\) and every edge incident with it; the remaining graph is denoted \(T-v\).

Deleting \(v\) leaves one component for each neighbor of \(v\). Indeed, the unique path from any other vertex to \(v\) reaches \(v\) through exactly one neighbor, and vertices reached through different neighbors cannot remain connected after \(v\) is removed. These component sizes add to \(n-1\), because they partition all vertices other than \(v\).

The threshold is inclusive: a component of size exactly \(n/2\) is allowed when \(n\) is even. When \(n\) is odd, component sizes are integers, so the largest allowed size is \(\lfloor n/2\rfloor\). This distinction matters in trees with two centroids.

Every Tree Has a Centroid

Proof. Start at any vertex \(v\). If every component of \(T-v\) has size at most \(n/2\), then \(v\) is a centroid and we are done. Otherwise, move from \(v\) to the neighbor \(u\) in a component \(C\) of \(T-v\) whose size \(k=|C|\) is greater than \(n/2\). There can be at most one such component, since two components each larger than \(n/2\) would contain more than \(n\) vertices in total.

Consider the components of \(T-u\). One component contains \(v\); it consists of the vertices outside \(C\), so its size is \(n-k\). Every other component lies within \(C-\{u\}\), so each has size at most \(k-1\). Since \(k>n/2\), we have \(n-k<k\), and also \(k-1<k\). Thus the size of every component of \(T-u\) is strictly less than \(k\).

Whenever the current vertex is not a centroid, repeat this move into its component of size greater than \(n/2\). At each move, the size of the oversized component at the new vertex is strictly smaller than the size of the oversized component that prompted the move. These are positive integers, so this process cannot continue indefinitely. It must reach a vertex with no component larger than \(n/2\), which is a centroid. For \(n=1\), the initial vertex already satisfies the condition because there are no components after deletion. \(\square\)

The proof gives a useful way to think about the search: if a component is too large, move into it. The component on the side just left behind becomes smaller than half, and the largest remaining piece strictly decreases at each move.

A Tree Has At Most Two Centroids

Proof. Suppose \(u\) is a centroid, and root the tree at \(u\). For each vertex \(x\ne u\), its parent is the neighbor immediately before \(x\) on the unique path from \(u\) to \(x\). Its children are its other neighbors. Let \(S_x\) be the set consisting of \(x\) and all vertices whose path from \(u\) passes through \(x\). This is the rooted subtree below \(x\).

For every child \(x\) of \(u\), the set \(S_x\) is exactly one component of \(T-u\). Because \(u\) is a centroid, \(|S_x|\le n/2\). Now suppose \(v\ne u\) is another centroid, and let \(x\) be the first vertex after \(u\) on the path from \(u\) to \(v\). If \(v\ne x\), then \(S_v\) is a proper subset of \(S_x\), so \(|S_v|\le |S_x|-1<n/2\). Deleting \(v\) leaves a component toward \(u\) containing all \(n-|S_v|\) vertices outside \(S_v\). Its size is greater than \(n/2\), contradicting that \(v\) is a centroid. Therefore any centroid other than \(u\) must be a child \(x\) of \(u\).

For such a child \(x\), the component of \(T-x\) toward \(u\) has size \(n-|S_x|\). If \(x\) is a centroid, this size is at most \(n/2\), so \(|S_x|\ge n/2\). Combined with \(|S_x|\le n/2\), this gives \(|S_x|=n/2\). There can be at most one child with a subtree of this size: two such child subtrees would be disjoint and together contain \(n\) vertices, although they are subsets of the \(n-1\) vertices other than \(u\). Thus there is at most one centroid besides \(u\); if it exists, it is adjacent to \(u\). \(\square\)

The proof also explains why two centroids are possible only when \(n\) is even: the component on the side of either centroid toward the other must have exactly \(n/2\) vertices. If \(n\) is odd, an integer component cannot have size \(n/2\).

Worked Examples

What the Centroid Measures—and a Common Pitfall

A centroid balances the sizes of the components produced by deleting a vertex. A Jordan center, by contrast, is defined using distances to the farthest vertex. These are different criteria: a vertex that balances the number of vertices on each side need not minimize the maximum distance. To test centroid status, count vertices in the components of \(T-v\); distances alone do not answer the question.

Common mistake: using a strict threshold. In the double-star example, one might wrongly reject \(u\) because deleting it leaves a component of size \(5\), and \(5\) is not less than \(10/2=5\). The definition requires component sizes to be at most \(n/2\), not strictly less than \(n/2\). Since \(5\le5\), \(u\) qualifies; the same reasoning shows that \(v\) qualifies too. Replacing “at most” with “less than” would incorrectly rule out both centroids.

The component-size viewpoint is useful whenever a tree must be split into parts that are as balanced as possible by vertex count. The existence proof guarantees that such a vertex is always available, and the second theorem sharply limits the search: there can be only one candidate, or two adjacent candidates when an edge divides the tree into equal halves.