Reachability as an Equivalence Relation

Reachability Between Vertices

In an undirected graph, one vertex can reach another when there is a path joining them. This simple relation records which pairs of vertices are connected by routes through the graph. It has an important logical structure: each vertex reaches itself, reachability works in either direction, and two successive routes can be combined into a route. These are exactly the three properties that make a relation an equivalence relation.

Throughout, graphs are finite, simple and undirected. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; its length is the number of edges in the sequence. We allow a path of length zero consisting of the single vertex \(v\). Its initial and final vertex are both \(v\). This convention does not assert that \(v\) has a loop: simple graphs have no loops.

A relation on a set is called an equivalence relation if it is reflexive, symmetric and transitive. Reflexivity means \(x\sim x\) for every element \(x\); symmetry means \(x\sim y\) implies \(y\sim x\); transitivity means \(x\sim y\) and \(y\sim z\) together imply \(x\sim z\). We will verify each property from the definition of reachability.

A Useful Fact About Combining Routes

When two paths meet at a vertex, following the first and then the second gives a walk. The resulting walk may repeat vertices, so it need not itself be a path. The following fact explains why that causes no problem. A walk allows repeated vertices, whereas a path does not.

Proof. Start with a walk \(v_0,v_1,\ldots,v_\ell\), where \(v_0=u\) and \(v_\ell=v\). If some vertex is repeated, choose indices \(i<j\) with \(v_i=v_j\). Delete the portion \(v_{i+1},\ldots,v_j\). If \(j<\ell\), the shortened sequence is still a walk: the step from \(v_i\) to \(v_{j+1}\) is valid because \(v_i=v_j\) and \(v_jv_{j+1}\) was an edge. If \(j=\ell\), the shortened walk still ends at \(u\)'s original destination \(v\), since \(v_i=v_\ell=v\). In either case, the endpoints are unchanged and the length decreases. Repeat this deletion whenever a vertex is repeated. The length is a nonnegative integer and decreases at every deletion, so the process stops. At that point there are no repeated vertices, and the resulting walk is a path. If the endpoints coincide, the length-zero path is permitted. \(\square\)

The Three Properties

Proof. We check the three properties.

Reflexivity. Let \(u\in V\). The sequence consisting only of \(u\) is a path of length zero from \(u\) to itself. Therefore \(u\sim u\).

Symmetry. Suppose \(u\sim v\). There is a path \(u=v_0,v_1,\ldots,v_k=v\). Read the same sequence in reverse: \(v=v_k,v_{k-1},\ldots,v_0=u\). Each consecutive pair remains adjacent because the graph is undirected, and the vertices remain distinct. Thus the reversed sequence is a path from \(v\) to \(u\), so \(v\sim u\).

Transitivity. Suppose \(u\sim v\) and \(v\sim w\). Choose a path from \(u\) to \(v\) and a path from \(v\) to \(w\). Following the first and then the second gives a walk from \(u\) to \(w\); the shared vertex \(v\) is included just once at the join. The walk may repeat other vertices, but by the lemma it contains a path with the same endpoints. Hence \(u\sim w\).

All three properties hold, so reachability is an equivalence relation. If \(V\) is empty, there are no vertices for which any of these conditions could fail, so the three universal statements hold vacuously. \(\square\)

The proof uses the assumptions in specific ways. The length-zero path supplies reflexivity without requiring a loop. Undirectedness is needed for reversing a path in the symmetry argument. For transitivity, the walks can be joined at their shared endpoint, and removing repetitions turns the joined walk into a path. In a directed graph, reversing a directed path need not give a directed path, so symmetry is not guaranteed.

Why the Length-Zero Convention Matters

The length-zero path is not a technical detail that can be omitted without changing the definition. It is what makes reachability reflexive in every graph, including graphs with isolated vertices. A positive-length path from a vertex back to itself would involve a cycle, and an isolated vertex has no such route. Requiring a positive length would therefore fail to establish \(v\sim v\) for every vertex.

The convention is also consistent with the rest of the proof. Reversing a length-zero path leaves the same path, so symmetry includes the case \(u=v\). When two paths are joined, one or both can have length zero. If the path from \(u\) to \(v\) has length zero, then \(u=v\), and the second path already joins \(u\) to \(w\). The transitivity conclusion still follows. The same reasoning applies if the second path has length zero. Thus no exception is needed for equal endpoints or trivial routes.

Common Pitfall

Wrong: “The graph has no loop at \(p\), so there is no path from \(p\) to \(p\), and reachability is not reflexive.” This confuses a loop, which would be an edge from a vertex to itself, with the length-zero path, which has no edges.

For example, take \(V=\{p,q\}\) and \(E=\{pq\}\). There is no loop at \(p\), but the one-vertex sequence \(p\) is a length-zero path from \(p\) to \(p\). Hence \(p\sim p\). The same argument gives \(q\sim q\), whether or not either vertex has any incident edges. Reflexivity comes from the path convention, not from the edge set.

Reachability is useful because it turns the question “Is there a route between these vertices?” into a relation with reliable structural rules. The theorem gives those rules directly: reverse a route to change its direction in an undirected graph, and concatenate routes to pass through an intermediate vertex. These conclusions depend only on the definition of path and the undirected nature of the graph.