Distance Depends on Connectivity
Graph distance is the length of a shortest path between two vertices. If the vertices are in the same connected component, at least one path joins them, so a shortest-path length exists. If they are in different components, there is no path at all. This tutorial makes that distinction explicit: a missing path is not a path of length zero or one, and the distance between the vertices must be recorded according to a stated convention.
Throughout, graphs are finite and simple. A path from \(u\) to \(v\) is a sequence of distinct vertices beginning at \(u\) and ending at \(v\), with consecutive vertices adjacent; its length is its number of edges. Vertices are in the same component when a path joins them. Equivalently, the components are the equivalence classes of the relation “joined by a path,” as established in the earlier material on reachability and components.
For a vertex and itself, the path of length zero gives \(d_G(u,u)=0\). For distinct vertices in the same component, the distance is a positive integer. Across different components, the distance is not a finite integer: under the first convention it is \(\infty\), while under the second it has no defined value.
What the Two Conventions Mean
The infinite-distance convention is convenient when a distance table should have an entry for every ordered pair of vertices. It records the absence of a path using the symbol \(\infty\), not as a large integer. In particular, \(\infty\) is not a possible number of edges in a path.
With the undefined-distance convention, a distance function is only being used for pairs in the same component. A table may show a dash or say “undefined” for other pairs, but the dash is explanatory notation, not a numerical distance. Do not replace these entries by zero: zero is reserved for a vertex’s distance from itself.
The conventions agree on every pair for which a path exists. They differ only in how they record pairs with no connecting path. In particular, a distance table made with one convention should not silently be interpreted using the other.
Proof. If \(u\) and \(v\) are in the same component, the definition of a component gives a path between them. The graph is finite, so there are only finitely many paths between these vertices, and the minimum of their lengths exists. Thus their distance is a finite integer under either convention. If they are in different components, no path joins them. The infinite-distance convention therefore assigns \(\infty\), while the undefined-distance convention assigns no value. These two cases establish both claims. \(\square\)
Distances Can Be Computed Component by Component
To calculate distances in a disconnected graph, first identify its components. Within each component, use shortest paths as usual. There is no need to search for a route through another component: such a route would itself connect the components, contradicting their being distinct.
Proof. A \(u\)-\(v\) path in \(G[C]\) is also a path in \(G\), because every edge of \(G[C]\) is an edge of \(G\). Conversely, consider any \(u\)-\(v\) path in \(G\). Every vertex \(w\) on the path is joined to \(u\) by the portion of the path from \(u\) to \(w\). Hence \(w\) is in the same component as \(u\), namely \(C\). The whole path therefore lies in \(G[C]\). The sets of \(u\)-\(v\) paths in the two graphs are identical, so their minimum lengths are equal. \(\square\)
This theorem justifies the componentwise procedure: find the distances within each component separately, then mark every cross-component pair as \(\infty\) or undefined according to the chosen convention.
Worked Example: A Path, an Edge, and an Isolated Vertex
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,bc,cd,ef\}\). The components are \(C_1=\{a,b,c,d\}\), \(C_2=\{e,f\}\), and \(C_3=\{g\}\). Indeed, the listed edges join consecutive vertices of \(C_1\), join \(e\) to \(f\), and give no edge incident with \(g\).
In \(C_1\), the only route between any two vertices follows the order \(a,b,c,d\). Counting its edges gives the following distance table:
| \(d_G\) | \(a\) | \(b\) | \(c\) | \(d\) |
|---|---|---|---|---|
| \(a\) | 0 | 1 | 2 | 3 |
| \(b\) | 1 | 0 | 1 | 2 |
| \(c\) | 2 | 1 | 0 | 1 |
| \(d\) | 3 | 2 | 1 | 0 |
For example, the path \(a,b,c\) has length \(2\), so \(d_G(a,c)=2\); the path \(a,b,c,d\) has length \(3\), so \(d_G(a,d)=3\). The other entries follow by counting consecutive edges along the same path. The component \(C_2\) has \(d_G(e,f)=d_G(f,e)=1\), since \(ef\) is an edge, and both diagonal entries are zero. For the singleton component, \(d_G(g,g)=0\).
There is no path from any vertex of \(C_1\) to a vertex of \(C_2\) or \(C_3\), and no path from \(e\) or \(f\) to \(g\). Thus all these cross-component entries are \(\infty\) under the infinite-distance convention, or undefined under the alternative convention.
Check: the distance from \(a\) to \(d\) is \(3\), not \(2\): the only route uses \(ab\), \(bc\), and \(cd\), three edges. The entry \(d_G(e,f)=1\) follows from the single edge \(ef\), while \(d_G(e,g)\) is not finite because no edge or path connects their components.
Worked Distances in More Than One Component
Worked Example: A Triangle and a Separate Three-Vertex Path
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,45,56\}\). The components are \(C_1=\{1,2,3\}\), a triangle, and \(C_2=\{4,5,6\}\), a path with edges \(45\) and \(56\).
Within the triangle, every pair of distinct vertices is adjacent. Each such distance is \(1\), and each diagonal distance is \(0\):
| \(d_G\) | 1 | 2 | 3 |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 3 | 1 | 1 | 0 |
Within the second component, \(d_G(4,5)=1\) and \(d_G(5,6)=1\), because those pairs are edges. The only path from \(4\) to \(6\) is \(4,5,6\), which has length \(2\). Hence \(d_G(4,6)=2\). The full table for this component is:
| \(d_G\) | 4 | 5 | 6 |
|---|---|---|---|
| 4 | 0 | 1 | 2 |
| 5 | 1 | 0 | 1 |
| 6 | 2 | 1 | 0 |
Every pair with one vertex in \(\{1,2,3\}\) and the other in \(\{4,5,6\}\) has no connecting path. For instance, \(d_G(2,6)=\infty\) under the infinite-distance convention, or is undefined under the alternative. The theorem above also explains why the triangle’s distances stay equal to \(1\) when computed in the whole graph: adding a separate component gives no new path between triangle vertices.
Check: the six off-diagonal entries within the triangle are all \(1\), since its three edges connect every distinct pair. In the path component, the two adjacent pairs have distance \(1\), and the endpoints \(4\) and \(6\) are separated by two edges, so their distance is \(2\). These values come directly from the edge set.
Worked Example: A Shorter Route Inside a Component
Let \(G=(V,E)\) have \(V=\{p,q,r,s,t,u\}\) and \(E=\{pq,qr,rs,sp,pr,tu\}\). The component \(C_1=\{p,q,r,s\}\) contains a 4-cycle with diagonal \(pr\), and \(C_2=\{t,u\}\) consists of one edge.
In \(C_1\), the edges \(pq,pr,ps,qr,rs\) give distance \(1\) for each corresponding pair. The remaining distinct pair is \(q,s\). It has no edge, but the paths \(q,p,s\) and \(q,r,s\) each have length \(2\), so its distance is \(2\). Thus the complete table is:
| \(d_G\) | p | q | r | s |
|---|---|---|---|---|
| p | 0 | 1 | 1 | 1 |
| q | 1 | 0 | 1 | 2 |
| r | 1 | 1 | 0 | 1 |
| s | 1 | 2 | 1 | 0 |
In \(C_2\), \(d_G(t,u)=d_G(u,t)=1\), because \(tu\) is an edge, and the self-distances are zero. Every distance between a vertex in \(C_1\) and one in \(C_2\) is \(\infty\) or undefined, depending on the convention.
Check: \(q\) and \(s\) are not adjacent, so their distance cannot be \(1\). The displayed paths of length \(2\) show that the distance is at most \(2\); the absence of edge \(qs\) shows it is greater than \(1\). Therefore it is exactly \(2\).
Disconnected Graphs and Diameter
For a connected graph, the diameter is the largest distance between two vertices. For a disconnected graph, there are two common ways to discuss diameter, and the distance convention affects which one is being used.
- If cross-component distances are set to \(\infty\), then any disconnected graph with at least two vertices has maximum distance \(\infty\). This is an extended-value convention; it does not describe a finite path length.
- Alternatively, report the diameter of each component separately, taking the largest distance among pairs within that component. This gives finite componentwise values, including diameter \(0\) for a singleton component.
- If cross-component distances are left undefined, a maximum over all vertex pairs is not defined. One can still report each component’s diameter separately.
For the empty graph, there are no vertex pairs, so a maximum distance over pairs is not defined without an additional convention. For a graph with one vertex, the only distance is its self-distance \(0\), so its diameter is \(0\). Stating the convention prevents these cases—and disconnected graphs more generally—from being hidden inside an unqualified claim about diameter.
Common Pitfall: Treating “No Path” as a Long Path
Suppose \(g\) is the isolated vertex in the first example and \(a\) belongs to the path component. A mistaken calculation might say, “There is no edge from \(a\) to \(g\), so \(d_G(a,g)=1\) by counting one step between them.” That calculation is wrong: a one-step path requires the edge \(ag\), and that edge is not in \(E\). Nor can a longer path exist, because any such path would connect their components.
The correction is to write \(d_G(a,g)=\infty\) under the infinite-distance convention, or to mark the distance undefined under the alternative. In particular, do not include such a pair among finite distances when computing a componentwise diameter. The first example shows the distinction concretely: the largest finite distance within \(\{a,b,c,d\}\) is \(3\), while there is no finite distance from \(a\) to \(g\).
A related check is useful when reading a distance table: every finite off-diagonal entry must be supported by an actual path of that length, and no shorter path may exist. If the vertices lie in different components, no finite entry can pass that check.
Check Your Understanding
Use the definitions and conventions in this tutorial. For each question, state whether you are using \(\infty\) or undefined for pairs in different components.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23\}\). Identify the components and give \(d_G(1,3)\), \(d_G(2,2)\), and the convention-appropriate value of \(d_G(1,4)\).
- Explain why a path between vertices in different components would contradict the definition of those components.
- For the graph in the second worked example, list all pairs in different components and state their distances under the infinite-distance convention.
- In the third worked example, give two shortest paths from \(q\) to \(s\), and explain why their distance is not \(1\).
- Why is the diameter of a disconnected graph not a finite maximum over all pairs if cross-component distances are left undefined?