Reachability in an undirected graph

Consider an undirected graph \(G\) and a relation \(R\) on its vertices such that \(uRv\) if and only if there is a path from \(u\) to \(v\).

Variant
Show that \(R\) is an equivalence relation.
Solution
The relation \(R\) is reflexive, because from each vertex \(v\) a path of zero length leads to \(v\).

If a path leads from \(u\) to \(v\), then reversing this path gives a path from \(v\) to \(u\). The relation \(R\) is therefore symmetric.

By connecting the path from \(u\) to \(w\) with the path from \(w\) to \(v\), we get a walk from \(u\) to \(v\). By omitting all the segments between two occurrences of the same vertex, the walk becomes a path. The relation \(R\) is therefore transitive.
Variant
What are the equivalence classes of this equivalence relation?
Solution
By the definition \(R[u]=\{v: uRv\}\) i.e. the set of vertices \(v\), which are reachable from \(u\) by a path. These sets are called components of connectivity.
Variant
How would this relation change if instead of the existence of a path we used the existence of a walk?
Solution
Each path is a walk and from each walk a path can be selected, as shown in the first variant, therefore both relations coincide.