Question

Show that a tree has either one center or two centers that are adjacent.

Short answer

A tree has either one center of has two centers that are adjacent.

Step-by-step solution

Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

The eccentricity of a vertex is the length of the longest simple path beginning at the vertex (assuming that the tree is unrooted).

A vertex is a center if there is no other vertex in the tree that has a smaller eccentricity.

At least one center

A tree has either one center of has two centers that are adjacent.

Let T be a tree with at least two vertices.

Since each vertex has a path to all other vertices in an unrooted tree, the eccentricity of a vertex always exists and thus there is also always at least one vertex with a minimal eccentricity, which implies that there is at least one center in T.

Two distinct centers are adjacent

Let u and v both be centers in the tree T with eccentricity e (both have the same eccentricity).

Let P be the simple path from u to v (note that this path is unique). Let c be a vertex (different from u and v) in the path P. c then requires an eccentricity of at least e and thus there exists a vertex w such that there is a unique simple path Q from c to w with length at least e.

We note that the path Q may follow the path P temporarily, but the path Q has to deviate from P after a while. Moreover, once path Q deviates from P, it cannot rejoin p as that would create a simple circuit (which is impossible in a tree). Since Q deviates from P at some point and cannot rejoin P, Q cannot follow P towards both u and v.

Let us assume that Q does not follow P towards u, then the simple path from u to c has length less than e, while the simple path c to w has a length of at least e. Combining these two paths, we then obtain that the path from u to w (by c) is a simple path with length more than e. However, by the definition of the eccentricity the longest simple path from u to another vertex has length e and thus we have obtained a contradiction. This then means that such a vertex c cannot exist, thus there are no other vertices in the path from u to v and thus u and v are adjacent.

More than \(2\) centers

Finally, one notes that if there are more than 2 centers, then there are least 3centers \({c_1}\), \({c_2}\) and \({c_3}\). By the previous section of the proof, we then know that \({c_1}\), \({c_2}\) and \({c_3}\) are all adjacent and thus these vertices form the complete graph \({K_3}\). However, \({K_3}\) contains a simple circuit and thus \({K_3}\) cannot be contained within a tree (by the definition of a tree), which implies that there cannot be more than 2 centers.