11.2 Walks, Paths, Cycles, and Connectivity

Section 11.1 described which pairs of vertices are adjacent. A network question usually asks for more than one local connection: Can a message travel from $A$ to $F$? Can a delivery route avoid repeating streets? Does one failed junction split the network?

To answer these questions, we join adjacent edges into routes.

A walk is the most general route

Let $G=(V,E)$ be an undirected graph. A walk from $v_0$ to $v_k$ is a finite vertex sequence

such that every consecutive pair is adjacent:

The length of the walk is its number of edges, namely $k$. The sequence contains $k+1$ vertex occurrences because it includes both the starting and ending vertices.

Suppose

Then

is a walk of length $4$. It uses edges $AB,BC,CA,AD$. A walk may repeat vertices and edges; it is the least restrictive route concept.

Trails, paths, closed walks, and cycles

We obtain more specific routes by forbidding repetition or requiring the route to close.

A trail is a walk that does not repeat an edge. Vertices may repeat.

A path is a walk that does not repeat a vertex. Because repeating an edge would also repeat its endpoints, every path is automatically a trail.

A walk is closed when its first and last vertices are equal. A circuit is a closed trail.

A cycle is a closed trail in which the first and last vertices are equal and every other vertex is distinct. In a simple undirected graph, a cycle has length at least $3$.

These definitions form a useful containment chain:

The reverse implications fail. For example:

Direction matters in a digraph. The sequence $u,v$ is a directed walk only when arc $(u,v)$ exists; the reverse arc $(v,u)$ cannot be assumed.

Simplifying a walk into a path

If a walk from $u$ to $v$ repeats a vertex, consider the portion between two consecutive appearances of that vertex. Removing that closed portion leaves another walk with the same endpoints and fewer edges.

Repeating this deletion eventually produces a walk with no repeated vertex—that is, a path. Therefore:

> If a walk exists from $u$ to $v$, then a path exists from $u$ to $v$.

This fact lets connectivity use paths even when the first route we discover contains detours.

Trace routes directly through a transit network. A live passport records repeated vertices, repeated edges, closure, and length, then classifies the route as a walk, trail, path, circuit, or cycle. Deliberately create near-misses and repair them.

Connected vertices and connected graphs

Two vertices $u$ and $v$ are connected when a path exists between them. A graph is connected when every pair of its vertices is connected.

In an undirected graph, “is connected to” behaves like an equivalence relation from Chapter 4:

• every vertex is connected to itself by the length-$0$ path;

• if a path runs from $u$ to $v$, reversing it gives a path from $v$ to $u$;

• if routes connect $u$ to $v$ and $v$ to $w$, joining them gives a walk from $u$ to $w$, which can be simplified to a path.

The resulting equivalence classes are the graph's connected components. A component is a maximal connected subgraph: it is connected, and no additional vertex from the graph can be included while preserving that component as one connected piece.

A subgraph $H=(V_H,E_H)$ of $G=(V,E)$ uses some vertices and some original edges, with

“Maximal” here does not mean “largest by size.” It means that the connected piece cannot be extended by another graph vertex. Different components may have different sizes.

Bridges and articulation vertices

Chapter 10 showed that every edge of a tree is a bridge. The same definition applies to any graph.

An edge is a bridge when deleting it increases the number of connected components. An edge on a cycle is not a bridge, because the rest of that cycle supplies an alternate route between its endpoints.

A vertex is an articulation vertex, or cut vertex, when deleting that vertex together with every incident edge increases the number of connected components.

These two failures are different. In the graph with edges

the triangles $A-B-C-A$ and $C-D-E-C$ protect their own edges with alternate routes. Edge $EF$ is a bridge. Vertex $C$ is an articulation vertex because it joins the two triangles, and vertex $E$ is an articulation vertex because it is the only attachment of $F$.

Deleting an isolated vertex does not create more components among the remaining vertices, so it is not an articulation vertex under this definition.

Finding components by systematic exploration

To find the component containing a start vertex $s$:

1. mark $s$ reached;

2. repeatedly inspect edges from reached vertices;

3. mark every newly encountered neighbor reached;

4. stop when no edge leads to an unreached neighbor.

The reached set is exactly the component containing $s$. If unreached vertices remain, choose one of them and repeat to find the next component. Section 11.3 will turn this idea into the breadth-first and depth-first search algorithms.

Operate a resilient communication network under failure. Remove one edge or one relay, observe components split in real time, identify bridges and articulation vertices, and restore redundancy with the fewest repairs.

From existence to search

Walks, trails, paths, and cycles distinguish which repetitions a route permits. Connectivity asks only whether some path exists, while bridges and articulation vertices expose single points of failure.

The exploration procedure above tells us what to do but not the exact order in which to do it. Section 11.3 will make the order explicit. Different frontier rules will produce breadth-first search and depth-first search, and edge weights will lead to shortest-path algorithms.