Radius Measures the Best Worst-Case Distance
For a vertex in a connected graph, its eccentricity records how far away its most distant vertex is. Comparing these values asks a different question from finding the graph’s farthest-apart pair: which vertex has the smallest possible distance to its farthest point? The minimum eccentricity is the graph’s radius, and the vertices attaining it are the central vertices. A distance table makes this comparison systematic: take the maximum in each row, then find the smallest of those maxima.
Throughout, graphs are finite and simple. Let \(G=(V,E)\) be a connected graph with at least one vertex. The distance \(d(u,v)\) is the length of a shortest \(u\)-\(v\) path. Connectedness ensures that this distance is finite for every pair of vertices. For a fixed vertex \(v\), its eccentricity is the greatest distance from \(v\) to any vertex of \(G\).
The maximum in the eccentricity definition means the farthest distance from the chosen vertex, not the average distance. The minimum in the radius definition then selects the vertex or vertices with the smallest such farthest distance. Because the graph is finite and has at least one vertex, these maxima and minimums are attained. In the one-vertex graph, the only distance is \(0\), so its radius is \(0\) and its sole vertex is central.
To read a distance table, treat each row as distances from its row vertex to all vertices, including itself. The diagonal entry is \(0\). First find the largest entry in every row; these are the eccentricities. Then take the smallest of those row maxima. Every row attaining that smallest value identifies a central vertex. The graph is undirected, so the table is symmetric, but each row still represents one vertex’s distances to the whole graph.
Finding the Center from a Distance Table
Proof. Fix any row index \(i\). Its entries are precisely \(d(v_i,v_j)\) for all vertices \(v_j\) of \(G\). By the definition of eccentricity, the largest entry in that row is \(\operatorname{ecc}(v_i)\). Taking the minimum of these row maxima over all \(i\) therefore gives \(\min_{v\in V(G)}\operatorname{ecc}(v)\), which is the definition of \(\operatorname{rad}(G)\). A vertex is central exactly when its eccentricity equals that minimum, so its row maximum must equal the radius. \(\square\)
This proposition explains the full calculation: no further operation on the distance table is needed. A useful check is to trace routes for the largest entries in a row. A claimed distance is correct only if a path of that length exists and there is no shorter path.
Worked Example: The Center of a Path
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). This is the path \(P_5\). Each pair of vertices has a unique path, so the distance from \(i\) to \(j\) is the number of edges between them along the listed path. The resulting distance table is:
| \(d(u,v)\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 1 | 0 | 1 | 2 | 3 |
| 3 | 2 | 1 | 0 | 1 | 2 |
| 4 | 3 | 2 | 1 | 0 | 1 |
| 5 | 4 | 3 | 2 | 1 | 0 |
The row maxima are \(\operatorname{ecc}(1)=4\), \(\operatorname{ecc}(2)=3\), \(\operatorname{ecc}(3)=2\), \(\operatorname{ecc}(4)=3\), and \(\operatorname{ecc}(5)=4\). The smallest is \(2\), so \(\operatorname{rad}(G)=2\) and \(C(G)=\{3\}\).
Check: From vertex \(3\), the distances to \(1,2,3,4,5\) are \(2,1,0,1,2\), giving eccentricity \(2\). Every other row maximum is \(3\) or \(4\), so no other vertex attains the radius. In particular, the endpoints are not central: their farthest vertices are four edges away.
Worked Example: Several Central Vertices
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\), the cycle \(C_6\). For each pair, the distance is the length of the shorter of the two routes around the cycle. This gives:
| \(d(u,v)\) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 3 | 2 | 1 |
| 2 | 1 | 0 | 1 | 2 | 3 | 2 |
| 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| 4 | 3 | 2 | 1 | 0 | 1 | 2 |
| 5 | 2 | 3 | 2 | 1 | 0 | 1 |
| 6 | 1 | 2 | 3 | 2 | 1 | 0 |
Every row maximum is \(3\). For example, from vertex \(1\), the farthest vertex is \(4\): both routes around the cycle have length \(3\). Each other row has the opposite vertex at distance \(3\) as well. Thus \(\operatorname{rad}(G)=3\), and \(C(G)=\{1,2,3,4,5,6\}\).
Check: The entries \(0,1,2,3,2,1\) in row \(1\) come from routes of lengths \(0,1,2,3,2,1\), respectively. No vertex is farther than three edges from \(1\), and the route \(1,2,3,4\) has length \(3\), so its eccentricity is exactly \(3\). The same opposite-vertex check applies to every row.
Worked Example: A Center Alongside a Symmetry
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,34,45\}\). Vertices \(1,2,3\) form a triangle, and the path \(3,4,5\) extends from vertex \(3\). The distance table is:
| \(d(u,v)\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 2 | 3 |
| 2 | 1 | 0 | 1 | 2 | 3 |
| 3 | 1 | 1 | 0 | 1 | 2 |
| 4 | 2 | 2 | 1 | 0 | 1 |
| 5 | 3 | 3 | 2 | 1 | 0 |
The row maxima are \(3,3,2,2,3\), respectively. Therefore \(\operatorname{rad}(G)=2\) and \(C(G)=\{3,4\}\). For instance, from \(3\), the distances to \(1,2,3,4,5\) are \(1,1,0,1,2\); the path \(3,4,5\) shows that the farthest distance is \(2\). From \(4\), the distances are \(2,2,1,0,1\), also with maximum \(2\).
Check: From \(1\), the route \(1,3,4,5\) has length \(3\), while every table entry in its row is at most \(3\); hence its eccentricity is \(3\). Vertex \(2\) has the same row maximum. From \(5\), the distances to \(1\) and \(2\) are both \(3\), using \(5,4,3,1\) and \(5,4,3,2\); its row maximum is also \(3\). Thus the two vertices with row maximum \(2\), and only those vertices, are central.
Why Symmetries Preserve the Center
An automorphism is a bijection from the vertex set of a graph to itself that preserves adjacency in both directions. Such a map changes vertex names without changing the graph’s connections. It follows that it also preserves distances and eccentricities, so a graph symmetry must send central vertices to central vertices.
Proof. Let \(u,v\in V(G)\). A shortest \(u\)-\(v\) path maps under \(\phi\) to a \(\phi(u)\)-\(\phi(v)\) path of the same length, because \(\phi\) preserves adjacency. Therefore \(d(\phi(u),\phi(v))\le d(u,v)\). The inverse map \(\phi^{-1}\) is also an automorphism, so applying the same argument to it gives \(d(u,v)\le d(\phi(u),\phi(v))\). Hence \(d(\phi(u),\phi(v))=d(u,v)\).
As \(u\) ranges over \(V(G)\), \(\phi(u)\) ranges over all of \(V(G)\), since \(\phi\) is a bijection. Thus the distances from \(\phi(v)\) to all vertices are exactly the distances from \(v\) to all vertices, possibly in a different order. Their maximum is the same, giving \(\operatorname{ecc}(\phi(v))=\operatorname{ecc}(v)\). Therefore a central vertex maps to a central vertex. Applying the same conclusion to \(\phi^{-1}\) shows that every central vertex is the image of a central vertex, so \(\phi(C(G))=C(G)\). \(\square\)
In the third example, swapping vertices \(1\) and \(2\) while fixing \(3,4,5\) is an automorphism: it preserves all five listed edges. The theorem accounts for their equal eccentricities, \(3\) and \(3\). More generally, symmetry can help check a distance table, but it does not replace the row-maximum calculation unless the relevant distances are also known.
Common Pitfalls
Reversing the minimum and maximum. Eccentricity is a maximum of distances from one vertex; radius is a minimum of those eccentricities. In \(P_5\), the row maximum at vertex \(1\) is \(4\). A common incorrect calculation is to take the smallest entry in that row, \(0\), and call it the eccentricity. That is the distance from \(1\) to itself, not its farthest distance. The correction is to take the row maximum first, giving \(\operatorname{ecc}(1)=4\), and only then compare row maxima to find the radius \(2\).
Confusing central and peripheral vertices. A central vertex attains the minimum eccentricity. A peripheral vertex attains the maximum eccentricity, which is the diameter. These are opposite comparisons, and the sets need not be the same. In \(P_5\), the center is \(\{3\}\), while vertices \(1\) and \(5\) have the largest eccentricity, \(4\). Always identify which extremum is being requested before reading the table.
Forgetting the connectedness assumption. This tutorial defines radius for a nonempty connected graph, where every distance used in the calculation is finite. For a disconnected graph, some vertex pairs have no path between them, so the distance-table procedure needs a convention beyond the one used here. Likewise, the empty graph has no vertex from which to form an eccentricity. The stated definitions therefore do not assign either graph a radius.
Check Your Understanding
For each question, use the definitions and, where relevant, find row maxima before comparing them.
- For the path with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\), find every eccentricity, the radius, and the center.
- For a connected graph whose distance table has row maxima \(4,2,3,2\), what is its radius, and which rows correspond to central vertices?
- Explain why the one-vertex graph has radius \(0\) and a nonempty center.
- In the triangle-with-tail example, verify that swapping vertices \(1\) and \(2\) preserves adjacency. What does the automorphism theorem imply about their eccentricities?
- Describe the two extrema involved in finding the radius: the one used within each row, and the one used across rows.