From Eccentricities to Radius and Diameter
Distances in a connected graph describe how far apart pairs of vertices are. Eccentricity summarizes all the distances from one vertex: it records the distance from that vertex to its farthest vertex. The radius and diameter then summarize the eccentricities across the whole graph. Their comparison follows from the elementary fact that every value in a finite set lies between its minimum and maximum. The important part is to keep track of which extremum defines which parameter.
Throughout, \(G=(V,E)\) is a finite, simple, connected graph with at least one vertex. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. For \(u,v\in V\), the distance \(d(u,v)\) is the length (number of edges) of a shortest \(u\)-\(v\) path. Connectedness ensures such a path exists for every pair, so all these distances are finite. In particular, \(d(v,v)=0\).
Because \(V\) is finite and nonempty, the maximum distance from each vertex exists, and the set of eccentricities is finite and nonempty. Thus both the minimum and maximum eccentricities are attained. A graph with just one vertex is included: its only distance is \(0\), so its eccentricity, radius, and diameter are all \(0\).
The Minimum and Maximum Bound Every Eccentricity
Proof. The vertex set \(V\) is finite and nonempty, and each \(e(v)\) is a finite integer. Therefore the nonempty finite set \(\{e(v):v\in V\}\) has a least element and a greatest element. By the definitions of minimum and maximum, each of these values is the eccentricity of at least one vertex. A vertex attaining the least value is central, and a vertex attaining the greatest value is peripheral. \(\square\)
The proposition ensures the extremal values come from actual vertices, not just from a bound that the eccentricities approach. More directly, for any chosen vertex \(v\), its eccentricity is one member of the set of all eccentricities. It therefore cannot be smaller than the least member or larger than the greatest member.
Proof. Let \(S=\{e(u):u\in V(G)\}\). By definition, \(\operatorname{rad}(G)=\min S\) and \(\operatorname{diam}(G)=\max S\). Since \(e(v)\in S\), the defining property of a minimum gives \(\min S\le e(v)\), and the defining property of a maximum gives \(e(v)\le\max S\). This proves the two inequalities for every \(v\). Since \(V(G)\) is nonempty, choose any \(v\in V(G)\). Then \(\operatorname{rad}(G)\le e(v)\le\operatorname{diam}(G)\), so in particular \(\operatorname{rad}(G)\le\operatorname{diam}(G)\). \(\square\)
This proof uses no special feature of paths or distances beyond the fact that each eccentricity is a value in a finite, nonempty set. The graph-theoretic definitions determine which set is being considered: first take the farthest distance from each vertex, then take the smallest and largest of those results. The theorem does not say that every vertex has eccentricity equal to the radius or diameter; it says that every eccentricity lies between them.
Worked Distance Calculations
Worked Example: The Path on Five Vertices
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). Between any two vertices there is just one path, so \(d(i,j)=|i-j|\). The full distance table is:
| \(d(i,j)\) | \(j=1\) | \(j=2\) | \(j=3\) | \(j=4\) | \(j=5\) | \(e(i)\) |
|---|---|---|---|---|---|---|
| \(i=1\) | 0 | 1 | 2 | 3 | 4 | 4 |
| \(i=2\) | 1 | 0 | 1 | 2 | 3 | 3 |
| \(i=3\) | 2 | 1 | 0 | 1 | 2 | 2 |
| \(i=4\) | 3 | 2 | 1 | 0 | 1 | 3 |
| \(i=5\) | 4 | 3 | 2 | 1 | 0 | 4 |
Taking the greatest entry in each row gives \(e(1)=4\), \(e(2)=3\), \(e(3)=2\), \(e(4)=3\), and \(e(5)=4\). The least of these values is \(2\), while the greatest is \(4\). Thus \(\operatorname{rad}(G)=2\) and \(\operatorname{diam}(G)=4\), and all five eccentricities lie in the interval from \(2\) to \(4\).
Check: In a path, the distance between \(i\) and \(j\) is \(|i-j|\). The greatest such distance from vertex \(i\) is \(\max(i-1,5-i)\), which gives \(4,3,2,3,4\) for \(i=1,2,3,4,5\), respectively. In particular, the endpoints \(1\) and \(5\) are four edges apart, and no pair is farther apart because the largest possible value of \(|i-j|\) for \(i,j\in\{1,2,3,4,5\}\) is \(4\).
Worked Example: A Star with a Strict Inequality
Let \(G=(V,E)\) have \(V=\{o,a,b,c,d\}\) and \(E=\{oa,ob,oc,od\}\). The vertex \(o\) is the center, and \(a,b,c,d\) are leaves. From \(o\), each leaf is one edge away, so \(e(o)=1\): the distances from \(o\) are \(0,1,1,1,1\). From a leaf, the center is one edge away and each of the other three leaves is two edges away. For example, from \(a\) the distances to \(o,b,c,d\) are \(1,2,2,2\), so \(e(a)=2\). The same calculation applies to each leaf, giving \(e(b)=e(c)=e(d)=2\).
Therefore the eccentricities are \(1,2,2,2,2\). Their minimum is \(1\) and their maximum is \(2\), so \(\operatorname{rad}(G)=1\) and \(\operatorname{diam}(G)=2\). The central vertex is \(o\), while all four leaves are peripheral.
Check: Any two distinct leaves have distance \(2\), via \(o\), and are not adjacent, so their shortest-path distance is exactly \(2\). No pair is farther apart: each leaf is distance \(1\) from \(o\), and the only pairs of distinct vertices not involving \(o\) are pairs of leaves. Thus the maximum distance, and hence the diameter, is \(2\). The radius is \(1\), since \(o\) has no vertex farther away than a leaf at distance \(1\), and every eccentricity is at least \(1\) because the graph has more than one vertex.
Worked Example: Equal Radius and Diameter
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\), a cycle on five vertices. From any vertex, its two neighbors are at distance \(1\), and the other two vertices are at distance \(2\), one in each direction around the cycle. For instance, from \(1\), the distances to \(2,5\) are \(1\) and the distances to \(3,4\) are \(2\). Hence \(e(1)=2\). The same pattern holds from each of the five vertices, so every eccentricity is \(2\).
Thus the minimum and maximum eccentricities are both \(2\), giving \(\operatorname{rad}(G)=\operatorname{diam}(G)=2\).
Check: Each vertex has exactly two vertices that are not itself or one of its two neighbors; these are the vertices two steps away around the cycle. They are not adjacent to the starting vertex, so their distance cannot be \(1\), and the two-edge routes show their distance is at most \(2\). Therefore each vertex has eccentricity exactly \(2\), confirming the radius and diameter by an independent check of all five starting vertices.
When Are the Radius and Diameter Equal?
Proof. If all vertices have the same eccentricity \(c\), then the minimum and maximum of the eccentricity set are both \(c\), so the radius and diameter are equal. Conversely, suppose \(\operatorname{rad}(G)=\operatorname{diam}(G)=c\). The theorem gives \(c=\operatorname{rad}(G)\le e(v)\le\operatorname{diam}(G)=c\) for every vertex \(v\). The only value between \(c\) and \(c\) is \(c\), so \(e(v)=c\) for every vertex. \(\square\)
The five-cycle illustrates this equality case, while the path and star illustrate strict inequality. Equality does not mean that all pairwise distances are the same. It means only that each vertex has the same greatest distance to another vertex. In the five-cycle, for example, each vertex has neighbors at distance \(1\) as well as vertices at distance \(2\).
Common Mistake: Reversing the Extremum
A frequent error is to treat the radius as the greatest eccentricity. For the path on five vertices, that mistaken calculation would take \(\max\{4,3,2,3,4\}=4\) as the radius. But \(4\) is the diameter: it is the maximum eccentricity. The radius is the minimum eccentricity, \(\min\{4,3,2,3,4\}=2\), attained at vertex \(3\). The corrected comparison is \(2\le 4\), not a comparison based on using the maximum twice.
Another useful distinction is between the two levels of maximum and minimum. Eccentricity itself is a maximum of distances from one fixed vertex. The radius then takes the minimum of those eccentricities, while the diameter takes their maximum. In symbols, the order of operations matters: first compute \(e(v)=\max_{u\in V}d(v,u)\) for each \(v\), then take the minimum or maximum over \(v\).
The connectedness and nonempty-vertex assumptions also matter for these definitions. Connectedness makes every distance finite, and a nonempty vertex set supplies eccentricities whose minimum and maximum can be taken. For a single-vertex graph, the definitions still work without exception: its only distance is \(0\), so its radius equals its diameter. The comparison is therefore valid even in this smallest case.
Check Your Understanding
Use the definitions of eccentricity, radius, and diameter to answer each question.
- In a finite, connected graph with eccentricities \(2,3,3,5\), what are the radius and diameter? Which values of eccentricity are guaranteed to lie between them?
- For the path \(P_4\) with vertices \(\{1,2,3,4\}\) and edges \(\{12,23,34\}\), calculate every vertex eccentricity and then find the radius and diameter.
- Explain why finiteness and nonemptiness ensure that a central vertex and a peripheral vertex exist.
- A student says that a graph has radius \(5\) because one vertex has eccentricity \(5\). What additional information is needed to justify that answer?
- Prove that if the radius and diameter of a finite, connected graph are equal, then every vertex has that common eccentricity.