The Bound and Its Idea
The diameter measures the greatest distance between two vertices, while the radius measures the smallest possible greatest distance from one vertex to all the others. To compare them, choose a vertex whose greatest distance is as small as possible. Any two vertices can be joined by going from the first to this chosen vertex and then from it to the second. Each part of this route has length at most the radius, so the distance between the original vertices is at most twice the radius.
Throughout, graphs are finite, simple and connected, and have at least one vertex. For vertices \(u,v\), the distance \(d(u,v)\) is the length of a shortest \(u\)-\(v\) path. In particular, \(d(u,u)=0\). The eccentricity of \(v\) is the greatest distance from \(v\) to any vertex. The graph's diameter is the greatest eccentricity, and its radius is the least eccentricity. A vertex whose eccentricity equals the radius is called a central vertex. Such a vertex exists because the graph is finite and nonempty, so its vertices have a minimum eccentricity.
The one-vertex graph is included in these definitions: its sole vertex has eccentricity \(0\), so both its diameter and radius are \(0\). The empty graph is excluded because there is no vertex from which to define eccentricity or a central vertex. Connectedness ensures that all distances used here are finite.
Routing Through a Chosen Vertex
The key observation does not require the chosen vertex to be central. It gives a bound in terms of that vertex's own eccentricity. The route obtained by concatenating two paths might repeat vertices, so it may be a walk rather than a path. This causes no difficulty: deleting the portions between repeated occurrences of a vertex turns a walk into a path of no greater length. Therefore the shortest-path distance is at most the length of the concatenated route.
Proof. Fix any vertices \(u,v\in V(G)\). Choose a shortest \(u\)-\(c\) path and a shortest \(c\)-\(v\) path. Their concatenation is a walk of length \(d(u,c)+d(c,v)\). Deleting any repeated sections gives a \(u\)-\(v\) path no longer than this walk, so \(d(u,v)\leq d(u,c)+d(c,v)\). By the definition of eccentricity, each of \(d(u,c)\) and \(d(c,v)\) is at most \(\operatorname{ecc}(c)\). Thus \(d(u,v)\leq 2\operatorname{ecc}(c)\). This holds for every pair \(u,v\), so taking the greatest such distance gives \(\operatorname{diam}G\leq 2\operatorname{ecc}(c)\). \(\square\)
Choosing a central vertex makes the proposition as strong as possible among bounds of this form: its eccentricity is the radius, the smallest eccentricity in the graph.
Proof. Since \(G\) is finite and nonempty, there is a vertex \(c\) whose eccentricity is minimum. By definition, \(\operatorname{ecc}(c)=\operatorname{rad}G\). Apply the proposition to this vertex to obtain \(\operatorname{diam}G\leq 2\operatorname{ecc}(c)=2\operatorname{rad}G\). This also covers the one-vertex graph: both sides are \(0\). \(\square\)
Worked Example: A Path Where Equality Holds
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,34,45\}\). The unique path between two vertices follows their order along the graph, so \(d(i,j)=|i-j|\). The distances from each vertex, listed in the order \(1,2,3,4,5\), are as follows:
From \(1\): \(0,1,2,3,4\), so \(\operatorname{ecc}(1)=4\). From \(2\): \(1,0,1,2,3\), so \(\operatorname{ecc}(2)=3\). From \(3\): \(2,1,0,1,2\), so \(\operatorname{ecc}(3)=2\). From \(4\): \(3,2,1,0,1\), so \(\operatorname{ecc}(4)=3\). From \(5\): \(4,3,2,1,0\), so \(\operatorname{ecc}(5)=4\).
The least of these eccentricities is \(2\), so \(\operatorname{rad}G=2\), attained at vertex \(3\). The greatest is \(4\), so \(\operatorname{diam}G=4\). Hence the bound is sharp here: \(\operatorname{diam}G=4=2\cdot 2=2\operatorname{rad}G\).
Check: The endpoints \(1\) and \(5\) are at distance \(4\). Routing through the central vertex \(3\) gives \(d(1,3)+d(3,5)=2+2=4\), using the distances computed above. No pair is farther apart: the largest entry in any distance list is \(4\). Thus the diameter calculation and equality both check out.
Worked Example: A Star Where Equality Holds
Let \(G\) have vertex set \(V(G)=\{c,a,b,d,e\}\) and edge set \(E(G)=\{ca,cb,cd,ce\}\). The vertex \(c\) is adjacent to each of the four leaves, and there are no edges between leaves.
From \(c\), the distance to each leaf is \(1\), so \(\operatorname{ecc}(c)=1\). From any leaf, the distance to \(c\) is \(1\), and the distance to each of the other three leaves is \(2\), by a path through \(c\). Thus each leaf has eccentricity \(2\). The minimum eccentricity is \(1\), giving \(\operatorname{rad}G=1\), and the maximum is \(2\), giving \(\operatorname{diam}G=2\).
Check: For example, \(d(a,e)=2\), since the route \(a,c,e\) has two edges and there is no direct edge \(ae\). Every pair is either a leaf and \(c\), at distance \(1\), or two leaves, at distance \(2\). Therefore the diameter is \(2=2\cdot 1=2\operatorname{rad}G\).
Worked Example: A Cycle Where the Bound Is Strict
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5,6\}\) and edge set \(E(G)=\{12,23,34,45,56,61\}\). Along this cycle, a shortest route between two vertices uses the shorter of the two directions around the cycle.
From vertex \(1\), the distances to \(1,2,3,4,5,6\), respectively, are \(0,1,2,3,2,1\). The greatest is \(3\), so \(\operatorname{ecc}(1)=3\). Rotating the labels around the cycle preserves adjacency and therefore preserves distances. Consequently, every vertex has eccentricity \(3\). Hence \(\operatorname{rad}G=3\) and \(\operatorname{diam}G=3\), and the theorem reads \(3\leq 2\cdot 3=6\), strictly.
Check: The displayed distance list shows a vertex at distance \(3\) from \(1\), namely \(4\), so the eccentricity of \(1\) is at least \(3\); every entry is at most \(3\), so it is exactly \(3\). Rotation gives the same calculation from every vertex. The largest pairwise distance is therefore \(3\), as claimed. The route from \(1\) to \(4\) through \(1\) has length \(0+3=3\); the general bound allows up to \(6\), but need not be attained.
What the Inequality Does—and Does Not—Say
The proof gives a useful way to interpret the factor of \(2\). For any central vertex \(c\), every vertex is at distance at most \(\operatorname{rad}G\) from \(c\). A route from \(u\) to \(v\) through \(c\) therefore has length at most \(\operatorname{rad}G+\operatorname{rad}G\). The shortest route between \(u\) and \(v\) can only be shorter than or equal to this particular route. The graph need not contain a shortest \(u\)-\(v\) path that passes through \(c\); the argument uses the route through \(c\) only to establish an upper bound.
In the path and star examples, a pair of vertices lies on opposite sides of a center and the route through that center is a longest shortest path, so equality occurs. In the cycle example, the theorem remains valid even though the actual diameter is much smaller than twice the radius. The inequality is a universal upper bound, not a claim that every graph reaches the bound.
Common Mistake: Reversing the Inequality
A common error is to confuse the radius with the diameter and write \(\operatorname{diam}G\leq\operatorname{rad}G\). The path on five vertices gives a concrete correction. Its radius is \(2\), while its diameter is \(4\), so the incorrect statement would require \(4\leq 2\), which is false. The valid conclusion is \(4\leq 2\cdot 2=4\). The factor of \(2\) is essential in general.
Another error is to use the route argument with distances from different intermediate vertices. The proof needs one common vertex \(c\): the path from \(u\) to \(c\) and the path from \(c\) to \(v\) join to make a route from \(u\) to \(v\). For the theorem, choose one central vertex and use it for every pair. Its eccentricity then bounds both parts of every such route by the same radius.
Check Your Understanding
Use the definitions and routing argument above to answer these questions.
- For a connected graph \(G\) and a vertex \(c\), explain why \(d(u,v)\leq d(u,c)+d(c,v)\) for any \(u,v\in V(G)\), even if the concatenated route repeats a vertex.
- What is the role of choosing a central vertex rather than an arbitrary vertex in the proof of \(\operatorname{diam}G\leq 2\operatorname{rad}G\)?
- For the path \(P_5\) with edges \(12,23,34,45\), compute the eccentricity of vertex \(2\) and use the proposition to give an upper bound on the diameter.
- In the six-vertex cycle example, why does the theorem give a valid bound even though the actual diameter is strictly less than twice the radius?
- For the one-vertex graph, compute its diameter and radius and verify the theorem directly.