Graph Diameter — Definition, Formula & Examples

Graph diameter is the greatest distance between any pair of vertices in a connected graph, where distance means the length of the shortest path connecting them.

For a connected graph $G = (V, E)$ , the diameter is defined as $\operatorname{diam}(G) = \max_{u,v \in V} d(u,v)$ , where $d(u,v)$ denotes the length of a shortest path (geodesic) between vertices $u$ and $v$ . If the graph is disconnected, the diameter is typically defined as infinite (or left undefined).

Key Formula

\operatorname{diam}(G) = \max_{u,\, v \in V} d(u, v)

Where:

$G$ = A connected graph with vertex set $V$ and edge set $E$
$d(u, v)$ = Length of the shortest path between vertices $u$ and $v$

How It Works

To find the diameter, first compute the shortest-path distance between every pair of vertices. Then take the maximum over all those distances. In practice, you can run BFS from each vertex in an unweighted graph or use algorithms like Floyd–Warshall for weighted graphs. The diameter tells you the worst-case communication delay or the farthest apart any two nodes can be in a network.

Worked Example

Problem: Find the diameter of the graph with vertices {A, B, C, D, E} and edges {AB, BC, CD, AE, EC}.

Step 1: Compute shortest-path distances from each vertex using BFS. For example, from A: d(A,B)=1, d(A,C)=2 (via A→E→C or A→B→C), d(A,D)=3 (via A→B→C→D), d(A,E)=1.

Step 2: Continue for all remaining pairs. From B: d(B,C)=1, d(B,D)=2, d(B,E)=2. From C: d(C,D)=1, d(C,E)=1. From D: d(D,E)=2.

Step 3: Identify the maximum distance across all pairs.

\operatorname{diam}(G) = \max\{1,2,3,1,1,2,1,2,1,2\} = 3

Answer: The diameter is 3, achieved by the pair (A, D).

Why It Matters

Graph diameter directly measures the worst-case efficiency of information flow in networks. In computer science, it determines latency bounds in distributed systems and peer-to-peer networks. It also appears in algorithm analysis, such as bounding the number of rounds in BFS-based algorithms.

Common Mistakes

Mistake: Using the longest path in the graph rather than the longest shortest path.

Correction: Diameter is defined using shortest-path distances. First find the shortest path between each pair of vertices, then take the maximum of those values.