Distance Measures the Shortest Route
When two vertices are joined by several paths, their distance records the length of the shortest one. In an unweighted graph, every edge counts as one step. Thus, distance depends on how many edges a route uses, not on how the graph is drawn or on how long an edge might look in a picture.
All graphs in this tutorial 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 the number of edges it uses. In particular, a path with \(k\) edges has \(k+1\) vertices. A length-zero path consists of one vertex, so it joins a vertex to itself.
The minimum matters: a path that happens to join the vertices need not be shortest. To calculate a distance, it is not enough to display one route. One must also rule out every shorter possibility. For example, if a candidate path has length three, showing that there is no edge between the endpoints rules out length one, but a separate argument must also rule out length two.
Why a Shortest Path Exists
Proof. Since \(u\) and \(v\) are connected, there is at least one path from \(u\) to \(v\). Consider the set of lengths of all such paths. Each length is a nonnegative integer, and the set is nonempty. Every nonempty set of nonnegative integers has a least element. That least length is therefore attained by a path in the set; it is \(d(u,v)\), and the path attaining it is a shortest path. \(\square\)
Finiteness also bounds the possible path lengths: a path cannot repeat vertices, so in a graph with \(n\) vertices it uses at most \(n\) vertices and at most \(n-1\) edges. The existence argument above does not require a graph to be connected as a whole; it applies to each connected pair of vertices. If a pair is not connected, there is no set of path lengths to minimize.
Proof. Let \(v_0,v_1,\dots,v_k\) be a shortest path from \(v_0\) to \(v_k\). Suppose that two nonconsecutive vertices \(v_i\) and \(v_j\) are adjacent, where \(0\le i<j\le k\) and \(j\ge i+2\). Replace the part \(v_i,v_{i+1},\dots,v_j\), which uses \(j-i\) edges, by the single edge \(v_iv_j\). The resulting route from \(v_0\) to \(v_k\) follows the original path up to \(v_i\), uses \(v_iv_j\), and then follows the original path from \(v_j\) onward. Its vertices are distinct because they form a subsequence of the original path with the intervening vertices omitted. It is a path, and its length is \(k-(j-i)+1<k\), since \(j-i\ge2\). This contradicts the assumption that the original path is shortest. Therefore no such edge exists. \(\square\)
This result is a useful warning when inspecting a proposed shortest path: an edge that skips over part of the path gives a strictly shorter route. The converse does not follow: a path with no such shortcut need not be shortest, because a different route elsewhere in the graph might be shorter.
Comparing Candidate Paths
Worked Example: Two Shortest Routes in a Diamond
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,24,34\}\). Find \(d(1,4)\), and identify all shortest paths from \(1\) to \(4\).
There are two evident candidate paths: \(1,2,4\) and \(1,3,4\). Each uses two edges, so each gives an upper bound of two on the distance: \(d(1,4)\le2\). To prove the distance is exactly two, rule out shorter paths. A path of length zero cannot join distinct vertices. A path of length one would require the edge \(14\), which is not in \(E\). Therefore no path has length less than two, and \(d(1,4)=2\).
To check that these are all the shortest paths, any path of length two from \(1\) to \(4\) must have the form \(1,w,4\), where \(w\) is adjacent to both endpoints. The neighbors of \(1\) are \(2\) and \(3\), and both are adjacent to \(4\). Thus the two length-two paths are exactly \(1,2,4\) and \(1,3,4\).
Check: The paths \(1,2,4\) and \(1,3,4\) each have \(3-1=2\) edges. The only possible shorter lengths for distinct vertices are zero and one; zero cannot join distinct endpoints, and edge \(14\) is absent. Hence the minimum length is two, attained by exactly the two paths listed.
A useful way to prove a lower bound is to ask what a very short path would require. For distinct nonadjacent vertices, a path of length two exists exactly when they have a common neighbor: the path must be \(u,w,v\), and both \(uw\) and \(wv\) must be edges. If there is no common neighbor, every path between them has length at least three. This observation can rule out short paths without listing every longer route.
Worked Example: Proving the Distance Is Three
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,bd,ce,de,df,ef\}\). Find \(d(a,f)\) and give a shortest path.
First, exhibit a route: \(a,b,d,f\) uses the edges \(ab,bd,df\), so it has length three and \(d(a,f)\le3\). There is also a route \(a,c,e,f\), using \(ac,ce,ef\), which has length three.
Now rule out shorter routes. The edge \(af\) is absent, so a path of length one does not exist. The neighbors of \(a\) are \(b,c\), while the neighbors of \(f\) are \(d,e\). These sets have no vertex in common, so there is no path of length two from \(a\) to \(f\). A length-zero path cannot join these distinct vertices. Thus every path has length at least three. Combined with the length-three routes, this proves \(d(a,f)=3\).
Check: The route \(a,b,d,f\) contains four vertices and three edges, so its length is \(4-1=3\). The endpoints are not adjacent, and their neighbor sets \(\{b,c\}\) and \(\{d,e\}\) are disjoint, excluding lengths one and two. The displayed route attains the resulting lower bound of three.
Several Candidate Routes May Differ
When comparing routes, count each edge traversed. A longer route can still be useful for finding the graph, but it does not determine the distance if another route is shorter. The distance is a property of the pair of endpoints in the whole graph, so the comparison must account for all possible shortcuts, not just the routes first noticed.
Worked Example: A Shortcut Changes the Distance
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,16\}\). Compare routes from \(1\) to \(5\) and find \(d(1,5)\).
One route follows the chain \(1,2,3,4,5\). It has four edges, so it gives \(d(1,5)\le4\). A different route is \(1,6,5\), which uses edges \(16\) and \(65\); it has length two. Therefore \(d(1,5)\le2\), so the length-four route cannot be shortest.
To establish the minimum, note that \(15\notin E\), so no path of length one joins the endpoints. The vertices \(1\) and \(5\) have the common neighbor \(6\), giving the length-two path \(1,6,5\). Since the endpoints are distinct, length zero is impossible. Consequently \(d(1,5)=2\). In fact, this is the only shortest path: the neighbors of \(1\) are \(2,6\), and the neighbors of \(5\) are \(4,6\), so their only common neighbor is \(6\).
Check: The path \(1,6,5\) has \(3-1=2\) edges. There is no edge \(15\), so length one is impossible, and length zero cannot join distinct vertices. The path therefore attains the minimum possible length, two.
Common Pitfalls
Counting vertices instead of edges. A path written \(u,w,v\) contains three vertices but has only two edges. Its length is two, not three. More generally, a path listed as \(v_0,v_1,\dots,v_k\) has \(k+1\) vertices and length \(k\), because its edges are the \(k\) consecutive pairs.
Stopping after finding a route. A route of length four proves only that the distance is at most four. It does not prove that the distance equals four: the third example had a route of length four but also a route of length two. To establish the exact distance, give a path of the proposed length and prove that no shorter path is possible.
Assuming uniqueness. A distance is a number, while a shortest path is a route attaining that number. There may be one shortest path or several. In the first example the distance is two, attained by two distinct paths.
Using the definition for a disconnected pair. Distance here is defined only for connected vertices. If no path joins the pair, there is no path length whose minimum could be taken. Do not select a finite distance simply because the graph itself has other paths.
Check Your Understanding
For each question, distinguish the length of a displayed path from the argument that the path is shortest.
- In the graph with \(V=\{p,q,r\}\) and \(E=\{pq,qr\}\), find \(d(p,r)\) and justify that no shorter path exists.
- In the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd,ad\}\), find \(d(a,c)\). Give two routes from \(a\) to \(c\) and compare their lengths.
- Can a path with five vertices have length five? Explain using the definition of path length.
- In the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,14\}\), find \(d(1,3)\) and list all shortest paths.
- Explain why an edge joining two nonconsecutive vertices of a proposed shortest path can show that the path is not shortest.