Walks, Paths, and Connectivity

The structure of connections within a graph determines its connectivity properties and provides the foundation for understanding graph traversal, reachability, and component structure.

DefinitionWalks and Paths

Let $G = (V, E)$ be a graph.

A walk of length $k$ is a sequence $v_0, e_1, v_1, e_2, \ldots, e_k, v_k$ where $e_i = \{v_{i-1}, v_i\} \in E$
A trail is a walk with distinct edges
A path is a walk with distinct vertices (except possibly $v_0 = v_k$ )
A cycle is a closed path with length at least 3

The distance $d(u,v)$ between vertices $u$ and $v$ is the length of the shortest path connecting them, or $\infty$ if no path exists.

DefinitionConnectivity

A graph $G$ is connected if every pair of vertices has a path connecting them. Otherwise, $G$ is disconnected. A maximal connected subgraph is a connected component.

The connectivity $\kappa(G)$ is the minimum number of vertices whose removal disconnects $G$ or reduces it to a single vertex. A graph is $k$ -connected if $\kappa(G) \geq k$ .

ExamplePath Properties

In the cycle graph $C_6$ with vertices $\{v_0, v_1, v_2, v_3, v_4, v_5\}$ , the sequence $v_0, v_1, v_2, v_3, v_4, v_5, v_0$ forms a cycle of length 6. The distance $d(v_0, v_3) = 3$ , achieved by the shortest path $v_0, v_1, v_2, v_3$ or $v_0, v_5, v_4, v_3$ .

The diameter $\text{diam}(G) = \max_{u,v \in V} d(u,v)$ measures the maximum distance between any two vertices in a connected graph. The girth is the length of the shortest cycle in $G$ , or $\infty$ if $G$ is acyclic.

DefinitionCut Vertices and Bridges

A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components
A bridge (or cut edge) is an edge whose removal increases the number of connected components

A connected graph with no cut vertices is 2-connected or biconnected.

Remark

For any connected graph $G$ , we have $\kappa(G) \leq \lambda(G) \leq \delta(G)$ , where $\lambda(G)$ is the edge connectivity (minimum edges to remove to disconnect) and $\delta(G)$ is the minimum degree. This inequality chain shows that vertex connectivity is the strictest measure of robustness.

Connectivity concepts extend naturally to directed graphs (digraphs), where we distinguish between strongly connected (every ordered pair reachable) and weakly connected (underlying undirected graph is connected). Understanding connectivity is essential for network reliability analysis, algorithm design, and structural graph theory.