Jordan Centers of Trees

Finding the Center by Pruning Leaves

In a tree, the most central vertex or vertices are those whose farthest vertex is as close as possible. This definition uses distances throughout the tree, but a simple procedure finds the answer without calculating every distance: repeatedly delete all leaves at once. The process stops at one vertex or at two adjacent vertices. We will prove that these remaining vertices are exactly the center of the original tree.

All graphs here are finite and simple. A tree is a connected graph with no cycles. A leaf is a vertex of degree \(1\). For a tree \(T\) and vertices \(u,v\), \(d(u,v)\) denotes the length of a shortest \(u\)-\(v\) path. The eccentricity of \(v\) is the greatest distance from \(v\) to any vertex of \(T\).

A single-vertex tree has eccentricity \(0\) at its only vertex, so that vertex is its center. In the pruning procedure, stop as soon as one or two vertices remain; in particular, do not delete both vertices of a two-vertex tree. When there are at least three vertices, delete all leaves simultaneously, and repeat on the remaining induced subgraph.

Why One Pruning Round Preserves the Center

Proof. First, \(T\) has a vertex of degree at least \(2\). Otherwise every vertex would have degree at most \(1\); in a connected graph with these degree bounds, there can be at most two vertices. Thus at least one vertex is not a leaf, and \(T'\) is nonempty. To see that \(T'\) is connected, take any two of its vertices and consider the path between them in \(T\). Every internal vertex on that path has at least two neighbors on the path, so it is not a leaf. The whole path remains in \(T'\). Since deleting vertices cannot create a cycle, \(T'\) is a tree.

Now fix \(v\in V(T')\). A vertex farthest from \(v\) in \(T\) must be a leaf: if a farthest vertex were not a leaf, the unique path from \(v\) to it could be extended by an edge away from \(v\), giving a more distant vertex. Let \(x\) be a farthest vertex. It is a deleted leaf, and its neighbor \(y\) is not a leaf: in a connected tree of at least three vertices, the neighbor of a leaf cannot itself have degree \(1\). Hence \(y\in V(T')\) and \(d(v,x)=d(v,y)+1\). This gives \(\operatorname{ecc}_{T'}(v)\geq\operatorname{ecc}_T(v)-1\).

For the reverse inequality, each vertex of \(T\) either survives, or is a deleted leaf \(z\) whose neighbor \(w\) survives. If \(z\) survives, its distance from \(v\) is at most \(\operatorname{ecc}_{T'}(v)\). If \(z\) is deleted, then \(d(v,z)=d(v,w)+1\leq\operatorname{ecc}_{T'}(v)+1\). Taking the maximum over all vertices of \(T\) proves \(\operatorname{ecc}_T(v)\leq\operatorname{ecc}_{T'}(v)+1\), and therefore gives the claimed equality.

Finally, let \(x\) be a deleted leaf and \(y\) its neighbor. In \(T-x\), which is a tree on at least two vertices, set \(M=\max_{z\in V(T)\setminus\{x\}}d(y,z)\). Then \(M\geq1\), \(\operatorname{ecc}_T(y)=M\), and \(\operatorname{ecc}_T(x)=M+1\), since every path from \(x\) to a different vertex starts with \(xy\). Thus \(x\) has larger eccentricity than the surviving vertex \(y\), so \(x\) is not a center. The eccentricities of all surviving vertices decrease by the same amount, \(1\), and no deleted vertex is a center. Consequently the centers of \(T\) are exactly the centers of \(T'\). \(\square\)

The Jordan Center Theorem

Proof. If the tree has one or two vertices, the stated stopping rule returns all its vertices. A one-vertex tree has its only vertex as center. In a two-vertex tree, both vertices have eccentricity \(1\), so both are centers and are adjacent.

Now suppose the tree has at least three vertices. By the lemma, one pruning round leaves a nonempty tree and preserves the center. It also leaves fewer vertices, because at least one leaf is deleted. Repeat the round whenever at least three vertices remain. Since the number of vertices is a positive integer that strictly decreases at each such round, the procedure must stop with one or two vertices. At every round the center set remains unchanged, by the lemma. The final tree has either one vertex, which is its center, or two adjacent vertices, both of which are its centers. Therefore the original tree has exactly the same center set: one vertex or two adjacent vertices, as claimed. \(\square\)

This proof also explains the specific stopping rule. If a two-vertex tree were pruned once more, both vertices would be deleted, even though both are centers. Stopping at two preserves the answer.

Pruning Trees Step by Step

Common Pitfall: Deleting Leaves One at a Time

The proof depends on deleting all leaves in the same round. For example, take the path \(P_4\) with vertex set \(\{a,b,c,d\}\) and edge set \(\{ab,bc,cd\}\). Its leaves are \(a\) and \(d\). Simultaneously deleting them leaves the edge \(bc\), so the two centers are \(b,c\). If instead one deletes \(a\), then \(b\) becomes a leaf in the smaller path \(b,c,d\). Deleting \(b\) next leaves \(c,d\); deleting \(c\) after that leaves \(d\). This one-at-a-time process ends at \(d\), which is not a center of the original path: its eccentricity is \(3\), while \(b\) and \(c\) each have eccentricity \(2\). The mistake is to treat leaves created midway through a round as if they had been leaves at its start.

Another important detail is that a pruning round subtracts \(1\) from the eccentricity of each surviving vertex, not necessarily from every vertex of the original tree. Deleted leaves are not centers; the lemma proves this separately. Together, these facts justify why the surviving center set is unchanged.