Walks, paths, and connected components

A walk of length $k$ is a vertex sequence $v_0,v_1,\ldots,v_k$ with consecutive vertices adjacent. A trail repeats no edge, while a simple path repeats no vertex. We allow a length-zero walk and path from a vertex to itself. Whenever a walk connects two distinct vertices, a simple path also does: if a vertex repeats, delete the closed portion between two occurrences. Each deletion shortens the walk, so the process terminates in a finite graph.

That deletion argument proves existence, not a formula for how many paths there are. It also explains why a shortest walk between distinct vertices cannot contain a repeated vertex: removing the intervening closed portion would shorten it. With nonnegative edge lengths, removing a closed portion does not increase length; with negative weights, shortest-walk questions may behave differently or have no finite minimum. Throughout the distance discussion here, every edge has unit length and the graph is finite, simple, and undirected.

Declare two vertices equivalent when a walk connects them. The length-zero walk gives reflexivity, reversing a walk gives symmetry, and concatenation gives transitivity. The equivalence classes are the connected components. Every edge stays within one component, and no vertex belongs to two components. This description also handles isolated vertices correctly: each isolated vertex is a component even though it participates in no positive-length walk.

Breadth-first search explores one component in distance layers. Start with a source at layer zero, then place its undiscovered neighbors at layer one, and continue from the current frontier. A vertex first discovered from layer $j$ receives layer $j+1$. Inductively, every path of at most $j$ edges has already been explored by the end of layer $j$, so first discovery gives the actual shortest distance. A predecessor edge for each discovered non-source vertex then supplies a concrete shortest-path witness.

Let $A$ be the zero-one adjacency matrix in a fixed vertex order. Its entry $A_{uv}$ records a length-one walk, and the entry of $A^2$ sums over every possible intermediate vertex. Induction with matrix multiplication shows that $(A^k)_{uv}$ counts length-$k$ walks. This formula includes repeated vertices and edges; it does not count only simple paths. The identity matrix at power zero matches the convention that each vertex has exactly one empty walk to itself.

For a directed graph, following arrows defines a reachability relation that is generally not symmetric. One-way reachability therefore does not give the undirected component partition just proved. Mutual directed reachability does define equivalence classes, called strongly connected components. Weak connectivity instead discards arrow direction before finding components. An application should name which notion it needs: the ability to send a request does not automatically guarantee a directed route for its response.