Recipe

Find a graph's diameter and radius

Use when: you're given a connected graph (or one component of a disconnected graph) and asked for its single worst-case and best-case distances

Goal: two numbers, diam(G) and rad(G), read off the full list of every vertex's eccentricity

Taught in Diameter and radius

1. 1

   Diameter and radius are only defined once every distance involved is finite. Check that the graph is connected before doing anything else -- eccentricity depends on reaching every other vertex, and a disconnected graph has no route between vertices in different pieces.

   Example

   Two separate triangles, P\text{-}Q\text{-}R and S\text{-}T\text{-}U, with no edge between the two: d(P,S) doesn't exist at all, since no walk connects them.

   • the graph is connected — continue straight to Step 2 on the whole vertex set.
   • the graph is disconnected — run Steps 2 through 5 separately inside each component; there is no single diameter or radius for the graph as a whole.

   Why: eccentricity, and everything built from it, is only meaningful when every distance it depends on is a finite number.

2. 2

   For each vertex, run breadth-first search from it and record the greatest distance reached -- that largest distance is this vertex's eccentricity, exactly as Section 5 defined it.

   Example

   On the two-triangles graph (edges A\text{-}B, A\text{-}C, B\text{-}C, C\text{-}D, C\text{-}E, D\text{-}E), BFS from A reaches B,C at distance 1 and D,E at distance 2, so \operatorname{ecc}(A)=2. Repeating from every vertex gives \operatorname{ecc}(A)=\operatorname{ecc}(B)=\operatorname{ecc}(D)=\operatorname{ecc}(E)=2 and \operatorname{ecc}(C)=1.

   Why: diameter and radius are both defined directly in terms of this list, so nothing in the next two steps can be found without it.

3. 3

   Scan the whole list of eccentricities from Step 2 and keep the largest value.

   Example

   The list \{2,2,1,2,2\} for A,B,C,D,E has largest entry 2, so \operatorname{diam}(G)=2.

   Why: the diameter is defined as the single worst-case distance found anywhere in the graph, which is exactly the biggest number on this list.

4. 4

   Scan the same list and keep the smallest value instead.

   Example

   The same list \{2,2,1,2,2\} has smallest entry 1, achieved by C, so \operatorname{rad}(G)=1.

   ⚡ Shortcut

   A vertex adjacent to every other vertex (a hub) always has eccentricity 1, the smallest an eccentricity can ever be in a graph with more than one vertex. Spotting a hub by eye, like C here, gives you the radius immediately without scanning the whole list.

   Why: the radius is defined as the single best-case distance anywhere in the graph, the smallest number on the list.

5. 5

   Confirm \operatorname{rad}(G) \leq \operatorname{diam}(G) \leq 2\operatorname{rad}(G) holds for the two numbers you just found.

   Example

   Here 1 \leq 2 \leq 2(1)=2 -- both inequalities hold, and the second one is tight.

   Why: this bound follows from the triangle inequality no matter what the graph looks like, so a violation means an eccentricity above was computed incorrectly.