From Routes in a Graph to a Distance
A graph records which pairs of vertices are joined directly. Even when two vertices are not joined by an edge, one may be reachable from the other by following several edges in succession. Counting the edges in a shortest such route gives a distance. The key point is that this count obeys the metric axioms, provided every pair of vertices can be connected by a path.
We use an undirected simple graph \(G=(V,E)\): \(V\) is a nonempty set of vertices, and \(E\) is a set of two-element subsets of \(V\), called edges. Thus an edge joins two distinct vertices, and there is at most one edge for each pair. A path of length \(n\), where \(n\) is a nonnegative integer, from \(x\) to \(y\) is a finite sequence \(x_0,x_1,\ldots,x_n\) with \(x_0=x\), \(x_n=y\), and \(\{x_{i-1},x_i\}\in E\) for every \(i=1,\ldots,n\). A path of length zero consists of one vertex, so it goes from that vertex to itself. A graph is connected if for every pair of vertices there is a path between them.
The minimum in this definition exists: for any fixed \(x,y\), connectedness gives at least one path, so the possible path lengths form a nonempty set of nonnegative integers. Every nonempty set of nonnegative integers has a least element. The graph distance is therefore a nonnegative integer, not just an infimum that might fail to be attained.
Why Shortest-Path Length Is a Metric
A metric on a set \(V\) is a function \(d:V\times V\to\mathbb{R}\) satisfying, for all \(x,y,z\in V\): nonnegativity and identity of indiscernibles (\(d(x,y)\geq 0\), with \(d(x,y)=0\) exactly when \(x=y\)); symmetry (\(d(x,y)=d(y,x)\)); and the triangle inequality (\(d(x,z)\leq d(x,y)+d(y,z)\)).
Proof. Fix \(x,y,z\in V\). By definition \(d_G(x,y)\) is a nonnegative integer, so it is nonnegative. If \(x=y\), the length-zero path gives \(d_G(x,x)=0\). If \(x\ne y\), every path from \(x\) to \(y\) has at least one edge: a length-zero path has the same initial and final vertex. Consequently \(d_G(x,y)\geq 1\), proving that \(d_G(x,y)=0\) exactly when \(x=y\).
Reversing any path from \(x\) to \(y\) gives a path from \(y\) to \(x\) of the same length, because edges are unordered pairs. In particular, reversing a shortest path gives \(d_G(y,x)\leq d_G(x,y)\). Reversing a shortest path from \(y\) to \(x\) gives the reverse inequality, so \(d_G(x,y)=d_G(y,x)\).
Finally, choose a shortest path from \(x\) to \(y\) and a shortest path from \(y\) to \(z\). Following the first path and then the second produces a path from \(x\) to \(z\) of length \(d_G(x,y)+d_G(y,z)\). This concatenated route need not be shortest, but the shortest length is no greater than the length of any route between the same endpoints. Hence \(d_G(x,z)\leq d_G(x,y)+d_G(y,z)\). All metric axioms hold. \(\square\)
Worked Distance Tables
Worked Example: Every Ordered Pair in a Three-Vertex Path
Let \(V=\{u,v,w\}\) and \(E=\{\{u,v\},\{v,w\}\}\). The graph is connected: \(u\) and \(v\) are joined by an edge, \(v\) and \(w\) are joined by an edge, and \(u\) reaches \(w\) along \(u,v,w\). Compute the distances for all ordered pairs, including the pairs from each vertex to itself.
The length-zero paths give \(d_G(u,u)=d_G(v,v)=d_G(w,w)=0\). Each listed edge gives \(d_G(u,v)=d_G(v,u)=1\) and \(d_G(v,w)=d_G(w,v)=1\). There is no edge \(\{u,w\}\), but \(u,v,w\) is a path of length \(2\). Since a path of length \(1\) would require that missing edge, \(d_G(u,w)=d_G(w,u)=2\).
| \(d_G(x,y)\) | \(y=u\) | \(y=v\) | \(y=w\) |
|---|---|---|---|
| \(x=u\) | 0 | 1 | 2 |
| \(x=v\) | 1 | 0 | 1 |
| \(x=w\) | 2 | 1 | 0 |
Check: the table has nine entries, one for every ordered pair in \(V\times V\). Its diagonal entries are \(0\), its entries for distinct adjacent vertices are \(1\), and its two entries for the nonadjacent pair \(u,w\) are \(2\). In particular, the distance from \(u\) to \(w\) is not \(1\), because no edge joins them.
Worked Example: Distances Around a Four-Cycle
Consider \(V=\{a,b,c,d\}\) with edges \(\{a,b\},\{b,c\},\{c,d\},\{d,a\}\). This is a connected graph. Each pair of neighboring vertices has distance \(1\). The opposite pairs \(a,c\) and \(b,d\) have no edge between them, but each can be joined by either of two paths of length \(2\). Thus \(d_G(a,c)=d_G(c,a)=2\) and \(d_G(b,d)=d_G(d,b)=2\).
These facts give all sixteen ordered-pair distances:
| \(d_G(x,y)\) | \(y=a\) | \(y=b\) | \(y=c\) | \(y=d\) |
|---|---|---|---|---|
| \(x=a\) | 0 | 1 | 2 | 1 |
| \(x=b\) | 1 | 0 | 1 | 2 |
| \(x=c\) | 2 | 1 | 0 | 1 |
| \(x=d\) | 1 | 2 | 1 | 0 |
Check: the four diagonal entries are zero. The four edges in the definition of \(E\) produce distance \(1\) in both orders, accounting for eight entries. The two opposite pairs produce distance \(2\) in both orders, accounting for the remaining four entries. Each distance \(2\) has a displayed two-edge route, and cannot be \(1\) because the corresponding pair is not an edge.
Worked Example: A Shortcut Changes the Distance Table
Let \(V=\{p,q,r,s,t\}\) and let the edges be \(\{p,q\},\{q,r\},\{r,s\},\{s,t\},\{t,p\},\{q,s\}\). These edges form a five-cycle with an extra edge from \(q\) to \(s\). The graph is connected because the five-cycle alone joins every vertex to every other vertex.
Each diagonal distance is \(0\), and each edge gives distance \(1\) in both orders. The nonadjacent unordered pairs are \(\{p,r\},\{p,s\},\{q,t\},\{r,t\}\). Their distances are all \(2\): routes of length \(2\) are \(p,q,r\), \(p,t,s\), \(q,s,t\), and \(r,s,t\), respectively. None of these pairs is an edge, so none has distance \(1\). Symmetry gives the distances in the reverse orders.
| \(d_G(x,y)\) | \(y=p\) | \(y=q\) | \(y=r\) | \(y=s\) | \(y=t\) |
|---|---|---|---|---|---|
| \(x=p\) | 0 | 1 | 2 | 2 | 1 |
| \(x=q\) | 1 | 0 | 1 | 1 | 2 |
| \(x=r\) | 2 | 1 | 0 | 1 | 2 |
| \(x=s\) | 2 | 1 | 1 | 0 | 1 |
| \(x=t\) | 1 | 2 | 2 | 1 | 0 |
Check: the table has \(5\cdot5=25\) entries: five zeros, twelve entries equal to \(1\) from the six edges, and eight entries equal to \(2\) from the four nonadjacent unordered pairs. For example, without the added edge \(\{q,s\}\), a route from \(p\) to \(s\) around the five-cycle has length \(2\), and the shortcut also gives \(p,q,s\) of length \(2\). In the table, the edge \(\{q,s\}\) also makes \(d_G(q,s)=1\), rather than the length \(2\) it would have had using only the five-cycle.
Disconnected Graphs and a Common Pitfall
If a graph is disconnected, some pairs of vertices have no path between them. For such a pair there is no finite path length to minimize, so the definition above does not give a real-valued distance on all of \(V\times V\). One can instead study graph distance separately on each connected component, where every pair is joined by a path. Alternatively, one can change the graph by adding edges between components; that changes the graph and may change the distances. Assigning the value \(+\infty\) to an unreachable pair is another convention, but the result is an extended distance, not a metric with values in \(\mathbb{R}\).
Common pitfall. In the three-vertex path \(u-v-w\), it is incorrect to calculate \(d_G(u,w)=1\) just because there is a route from \(u\) to \(w\). A route is not necessarily a single edge. The route \(u,v,w\) uses two edges, so its length is \(2\). Since \(\{u,w\}\notin E\), there is no path of length \(1\), and therefore \(d_G(u,w)=2\). The distinction between a path and an edge is exactly what makes shortest-path distance useful: it measures the number of steps needed, not merely whether a route exists.
For a one-vertex graph, connectedness holds and the only distance is \(d_G(x,x)=0\); the metric axioms still apply. The nonempty assumption excludes the empty vertex set from the stated theorem, avoiding a convention about whether it counts as connected. On any nonempty connected graph, including an infinite one, the proof works because each particular pair has at least one finite path and the set of its possible lengths is a nonempty set of nonnegative integers.
Check Your Understanding
For each question, use the definition in terms of paths and count edges rather than vertices.
- In the path with vertices \(a,b,c,d\) and edges \(\{a,b\},\{b,c\},\{c,d\}\), find \(d_G(a,d)\) and explain why no shorter path is possible.
- In a triangle with vertices \(x,y,z\), find the distance between every pair of distinct vertices, and state the diagonal distances.
- Give a connected graph in which two distinct vertices have distance \(3\), and exhibit a shortest path between them.
- Why does reversing a path prove symmetry of graph distance only because the graph is undirected?
- In a disconnected graph, what goes wrong if one tries to define the distance between vertices in different components by the shortest-path rule?