Graph Distance — Definition, Formula & Examples

Graph distance is the number of edges in the shortest path between two vertices in a graph. If no path exists between the vertices, the distance is defined as infinity.

Given a graph $G = (V, E)$ and two vertices $u, v \in V$ , the distance $d(u, v)$ is the minimum number of edges in any $u$ – $v$ path. If no such path exists, $d(u, v) = \infty$ . By convention, $d(v, v) = 0$ for all $v \in V$ .

Key Formula

d(u, v) = \min\{\,|P| : P \text{ is a } u\text{–}v \text{ path in } G\,\}

Where:

$d(u, v)$ = Distance between vertices u and v
$|P|$ = Number of edges in path P
$G$ = The graph containing the vertices and edges

How It Works

To find the distance between two vertices, identify all paths connecting them and count the edges in each path. The shortest such count is the distance. In practice, breadth-first search (BFS) efficiently computes the distance from a source vertex to every other vertex in an unweighted graph. BFS explores vertices layer by layer, so the first time it reaches a vertex, it has found the shortest path to that vertex.

Worked Example

Problem: Consider a graph with vertices {A, B, C, D, E} and edges {A–B, A–C, B–D, C–D, D–E}. Find the distance from A to E.

List paths from A to E: Path 1: A → B → D → E (3 edges). Path 2: A → C → D → E (3 edges).

Select the shortest: Both paths have 3 edges. No shorter path exists because E is only reachable through D, and D is at distance 2 from A.

d(A, E) = 3

Answer: The graph distance from A to E is 3.

Why It Matters

Graph distance is central to network analysis — measuring degrees of separation in social networks, computing routing tables in computer networks, and analyzing molecular structures in computational chemistry. Algorithms like BFS and Dijkstra's algorithm rely on this concept to solve shortest-path problems efficiently.

Common Mistakes

Mistake: Counting vertices instead of edges when measuring distance.

Correction: Graph distance counts edges, not vertices. A path through 4 vertices has 3 edges, so the distance is 3, not 4.