Motivation: how far away is the farthest vertex?
A connected graph guarantees a route between every pair of vertices. It does not say that all starting points are equally convenient. On a long path, an endpoint is far from the opposite endpoint, whereas a middle vertex is reasonably close to both ends. To make this comparison precise, fix a starting vertex, measure its distance to every vertex, and keep the largest distance. We then ask which starting vertices make that largest distance as small as possible.
For a general graph, several different shortest routes can compete. A tree has a unique path between each pair, so branches cannot provide shortcuts. This restriction makes a remarkably complete answer possible: the ends of any longest path determine every vertex's farthest distance, and the middle of that path determines the center. A second argument explains why repeatedly removing all leaves finds the same vertices.
Distance and three different extrema
Throughout, graphs are finite, simple, undirected and unweighted. Assume that is connected and has at least one vertex.
Definition 1.4.1
(Distance in a connected graph)
The distance is the minimum number of edges in a – path; . Connectivity ensures that this number is finite. Subscripts may be omitted when the graph is clear.
Distance is symmetric and is positive between distinct vertices. It also satisfies the triangle inequality
Indeed, concatenate shortest paths from to and from to . The resulting walk has the displayed total length. Removing repetitions produces a path no longer than that walk. The inequality need not be an equality: the best route through need not be a shortest route from to .
Definition 1.4.2
(Eccentricity, diameter, radius and center)
The eccentricity of a vertex, the diameter, the radius, and the center are respectively
Thus eccentricity fixes one endpoint before taking a maximum; diameter allows both endpoints to vary; radius chooses the best starting vertex against its worst destination. The center is a set of vertices, not a numerical distance. Finiteness and nonemptiness make all these extrema attained. A one-vertex graph has diameter and radius zero, and its sole vertex is its center. We do not assign a finite graph-wide radius to a disconnected graph here; its components can be studied separately.
Theorem 1.4.3
(The general radius–diameter bounds)
Every finite nonempty connected graph satisfies
Proof
(The triangle inequality at a diameter pair)
Choose vertices at distance . For any , the triangle inequality gives . Minimize over and use that distances are integers. The upper bound follows because every eccentricity is at most the diameter. We will prove that trees always attain the lower bound. This is an extra theorem about trees, not part of the definition of radius.
A diameter controls every branch of a tree
Let be a nonempty tree and let
be a path whose length is the diameter. Write and . Such a path exists: distances are attained, and in a tree the unique path between a diameter pair is also a longest simple path.
Every vertex has a unique attachment vertex on : the path from to first enters there, and every path from to a vertex of enters at that same vertex. For , use itself. To justify uniqueness off the path, consider a component after deleting the vertices of . It must attach to somewhere by connectivity. Two distinct attaching edges, whether their endpoints on coincide or differ, would combine a path inside the component with part of to form a cycle. A tree forbids this. The same unique-path property proves that a route to either endpoint goes through the attachment.
Put . Distances to the two endpoints are therefore and . Neither can exceed , so
This inequality is the useful information hidden in the word “diameter”. A long branch cannot hang near an end of , since it would create a still longer path to the opposite end. A branch near the middle may be longer, but its height is still constrained by both ends.
Theorem 1.4.4
(Two diameter endpoints determine all eccentricities)
If are endpoints of any diameter of a finite nonempty tree, then for every vertex ,
More explicitly, if attaches to at distance , then
Proof
(Bounding every distance through the attachments)
Fix and an arbitrary vertex , with attachment coordinates and heights . Going from to , along to , and then to gives a walk of length . When the two branches overlap, this walk may retrace edges; it still gives an upper bound for distance. If , the branch bound gives . If , the other bound gives . Thus
On the other hand, and , so one of these endpoints attains that upper bound. Maximizing over proves both formulas. The proof includes : then the tree has one vertex and all quantities are zero.
Proof X-ray
Where the maximality of the diameter is used
The upper bound is the whole content, and it rests on one inequality. The route is merely a walk, so it only bounds the distance from above, and no tree property is needed there. The tree enters through unique attachments, which make and well defined. The maximality of enters through the branch bound , used once in each case: when attaches on the side of , and when it attaches on the side. The lower bound costs nothing, because the endpoints themselves realize and . On a cycle attachments are not unique, which is exactly where the four-cycle counterexample below escapes.
Corollary 1.4.5
(Radius and center of a tree)
Let be a diameter path of a finite nonempty tree . Then . If , the center is ; if , it is .
Proof
(The middle of a diameter)
The formula separates the cost of leaving the diameter, namely , from the cost of choosing a position along it, namely . The latter is minimized at the integer positions nearest , where it equals . Any vertex off the diameter has , so it cannot attain that minimum.
Consequently . If , the center is the single vertex . If , it is the adjacent pair . Different diameter paths may exist, but this argument describes the intrinsic set from any one of them, so their middle vertex or pair must agree.
Our allowed locations are vertices. For a path of length five, the two middle vertices have eccentricity three; the interior midpoint of their joining edge is not an additional vertex with eccentricity two and a half.
Concept lensAlgorithmic
Two searches find a diameter and its middle
The attachment bounds also show that a farthest vertex from any vertex is a diameter endpoint. Hence a breadth-first search from an arbitrary vertex finds a vertex with ; a second search from finds a farthest vertex and the – path, which is a diameter path. By the corollary, its middle vertex or middle pair is the center. Two linear-time searches thus compute the same set that pruning computes.
Why removing leaves preserves the center
Definition 1.4.6
(Leaves and simultaneous pruning)
A leaf is a vertex of degree one. If a tree has at least three vertices, remove all its leaves simultaneously, and let be the induced graph on the retained vertices.
There is at least one retained vertex: otherwise a connected tree of order at least three would have every degree at most one. The path between two retained vertices stays retained, since each internal vertex on that path has at least two neighbors. Hence is again a nonempty tree, and distances between retained vertices do not change.
Theorem 1.4.7
(One complete pruning round subtracts one from eccentricity)
For a tree with at least three vertices and its simultaneously pruned tree , every retained vertex satisfies
Proof
(Each removed leaf hangs on a retained vertex)
Each removed leaf has a retained neighbor. Otherwise two adjacent leaves would form the whole connected tree, contrary to its order. Thus every removed vertex is at distance at most from a fixed retained , and every retained vertex is at distance at most . This proves .
For equality, choose farthest from within . If has more than one vertex, then and has just one neighbor in : a second neighbor could extend the unique – path. But was retained, so its degree in was at least two; it has a removed leaf neighbor. Appending that edge gives distance from . If has only one vertex, all its neighbors in were removed, and the same conclusion holds with .
It remains to exclude deleted vertices from the old center. For a leaf with neighbor , every path from to another vertex first goes to . There is a vertex other than , so a farthest vertex from can be chosen different from . Therefore , and cannot minimize eccentricity. All old center vertices are retained, and all retained eccentricities decrease by the same amount. Their minimizers, and hence the center, are unchanged.
Proof X-ray
Why one round lowers every eccentricity by the same amount
The order hypothesis is spent once: with at least three vertices, no removed leaf is adjacent only to another leaf, so every deleted vertex hangs one edge below a retained vertex. That gives the upper bound. Equality needs a removed leaf beyond a farthest vertex of , and such a vertex is a leaf of (or its only vertex) that had degree at least two in . The shift is uniform over retained vertices, so their ranking and its minimizers survive. Deleted leaves are excluded separately, each being one step worse than its neighbor.
The algorithm and its stopping rule
If one or two vertices remain, return them all. A one-vertex tree has one center; a two-vertex tree has both endpoints as centers. Otherwise remove a complete round of current leaves and repeat. A finite nontrivial tree has at least two leaves, as seen by taking endpoints of a longest path, so the process terminates. Center preservation proves that its final vertex or adjacent pair is exactly the center of the original tree.
With adjacency lists, initialize the current degrees and a queue of leaves. At each round record the queue's current size and process exactly that many vertices, decrementing degrees of surviving neighbors and adding newly created leaves for the next round. Do not process the new leaves in the same round. Stop when the active vertex count is at most two, and return the active vertices; a final singleton has degree zero and still must be returned. Each removed vertex is scanned once, and the total number of adjacency entries is . Degree updates, queue operations and a final active-vertex scan therefore use work and storage. Rescanning all vertices to discover leaves in every round would not establish this linear bound.
Worked examples
Worked example 1.4.8
(A path with two central vertices)
For , the diameter is five. The eccentricities in this order are , since . Thus the radius is three and the center is . Pruning removes , then , and stops at that adjacent pair. A vertex can belong to the center without being the unique best location.
Worked example 1.4.9
(A branch can tie for a diameter without moving its midpoint)
Take the path and attach to and to . The original path has length six. A route from to any path vertex has length at most ; the shorter branch vertex and pairs on the original path cannot give more. Hence the diameter is still six. Both – and – are diameter paths. The formula gives , and . The center is , which is the midpoint of either diameter. The branch length was essential: a much longer branch would invalidate the original diameter choice.
Worked example 1.4.10
(Unequal degrees do not determine the center)
Start with , attach to and to . The four leaves are ; both have degree three. Leaf-to-leaf distances are at most three, and , so the diameter is three. Both have eccentricity two and every leaf has eccentricity three. One simultaneous round removes all four leaves and leaves the center edge . In contrast, on a long path all internal degrees equal two although only its middle vertex or pair is central. Degrees alone do not encode distance to the ends.
Counterexamples and common mistakes
Counterexample mode
A cycle breaks the tree conclusions
On the four-cycle , every vertex has eccentricity two. Diameter and radius are both two, and all four vertices form the center. The diameter endpoints are each only distance one from , although . Thus neither the endpoint formula nor nor the one-or-two-centers conclusion extends to all connected graphs. This cycle has no leaves, so leaf pruning makes no progress. The tree proof used unique attachment paths, which a cycle does not have.
Even within trees, the pruning rule has a hypothesis that is easy to drop.
Counterexample mode
Deleting newly created leaves immediately can remove the center
On , delete , then the newly exposed leaf , then . Two vertices remain, but they are , whereas the original center is . Arbitrary sequential deletion does not preserve the center. A correct round fixes its leaf set before removing anything; here the successive simultaneous rounds are and .
Common mistake
(A diameter counts edges, not vertices)
A diameter counts edges, not vertices: the path has six vertices and diameter five. Distance always means a shortest path, even though in a tree its diameter path is also a longest simple path. A leaf need not be a diameter endpoint; in the second practice exercise the leaf has eccentricity three, less than the diameter four.
Common mistake
(The center minimizes the greatest distance, not the total)
Minimizing the largest distance is a different optimization problem from minimizing the sum of distances. In the final exercise the center has greatest distance two and total distance , while has greatest distance three and the smaller total .
Practice
Quick check
(On the path , find the diameter, radius, center and eccentricity of . List all simultaneous pruning rounds.)
Solution · Answer
The diameter is eight, the radius is four, the center is and . The rounds remove , , and , leaving . Each round uses the leaves of the tree at its beginning.
Quick check
(Take and attach one additional leaf to . Find the center and . Does lie at the end of any diameter? List the pruning rounds.)
Solution · Answer
The diameter is four, attained by –, and its midpoint is . The distances from to are both three, so . A diameter endpoint must have eccentricity equal to the diameter; hence this leaf is not a diameter endpoint. Remove , then , leaving .
Quick check
(Prove that adjacent vertices in any finite nonempty connected graph satisfy . Must their eccentricities be different?)
Solution · Answer
For every , . Taking maxima gives ; reverse for the other inequality. The two eccentricities can be equal: both vertices of a two-vertex tree have eccentricity one, and every vertex of the four-cycle has eccentricity two. Adjacency controls the difference but need not force a strict improvement toward a center.
Quick check
(Add one new leaf adjacent to a vertex of a nonempty tree . Prove that the new diameter is . Apply this to attaching a leaf at or at of , and determine the new centers.)
Solution · Answer
Distances between old vertices do not change, because the new leaf cannot be internal to a path between them. Old pairs contribute maximum ; pairs involving contribute maximum . These exhaust all pairs and prove the formula. For the five-vertex path, and , so a leaf at leaves diameter four and center . At , , so the new diameter is five; the path has middle vertices , the new center. The diameter formula alone gives a number; a diameter path then identifies its center.
Quick check
(Begin with and attach four new leaves to . Identify the center and compare the sums of distances from and from . Does the center necessarily minimize this sum?)
Solution · Answer
Every new leaf is at distance four from , and all vertex pairs have distance at most four. Thus – is a diameter and the center is , with eccentricity two. The sum from is , where the last term accounts for four new leaves. The sum from is . Therefore the center need not minimize total distance: has a smaller sum while its greatest distance, three, is larger than 's greatest distance, two.