Graph Theory — Paths, Cycles, Connectivity

Paths, cycles, and connectivity describe how vertices in a graph link to one another. A path is a walk with no repeated vertices, a cycle is a closed path, and a graph is connected if every pair of vertices is joined by a path. Applies to network reliability, routing, circuit design, and any system modelled as nodes with relationships. Foundational results trace to Euler (1736), Menger (1927), and Whitney (1932).

Given a graph $G = (V, E)$ with vertex set $V$ and edge set $E$ , the most basic structural questions are: can you travel from one vertex to another, and how robustly? A path is a sequence of distinct vertices each adjacent to the next; a cycle closes such a sequence back to its origin. Connectivity quantifies how many vertices or edges must be removed to disconnect the graph, capturing notions of fault-tolerance and bottlenecks. These ideas underpin nearly all of graph theory and its applications, from internet routing to molecular structure. A surprising fact: Menger's theorem reveals that the maximum number of disjoint paths between two vertices exactly equals the minimum number of vertices whose removal separates them — a duality that prefigures the entire theory of network flows.

The Core Insight

Reachability and robustness are two sides of the same coin. The existence of a single path tells you two vertices are connected; the existence of many independent paths tells you the connection is resilient. Menger's theorem fuses these into one exact min-max equation: the bottleneck (smallest cut) equals the throughput (largest set of disjoint paths). Cycles, meanwhile, are precisely the redundant structure — a connected graph with no cycles (a tree) is connectivity at its leanest, and every extra edge creates exactly one cycle.

Formal Statement

Walks, Trails, Paths, Cycles

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

A walk of length $k$ is an alternating sequence $v_{0} e_{1} v_{1} e_{2} \dots e_{k} v_{k}$ where each edge $e_{i}$ joins $v_{i - 1}$ and $v_{i}$ .
A trail is a walk with no repeated edge.
A path is a walk with no repeated vertex (hence no repeated edge).
A closed walk has $v_{0} = v_{k}$ .
A cycle is a closed walk of length $\geq 3$ with no repeated vertex except $v_{0} = v_{k}$ .

The length of a path or cycle is its number of edges.

For a path on $n + 1$ vertices, the length is:

ℓ (P) = ∣ E (P) ∣ = ∣ V (P) ∣ - 1

⟳A path visits

n + 1

distinct vertices in sequence; consecutive pairs define edges, giving one fewer edge than vertices.

Connectivity

A graph $G$ is connected if for every pair $u, v \in V$ there exists a $u$ – $v$ path. A maximal connected subgraph is a connected component.

The vertex connectivity $κ (G)$ is the minimum number of vertices whose removal disconnects $G$ (or reduces it to a single vertex). The edge connectivity $λ (G)$ is the minimum number of edges whose removal disconnects $G$ .

A graph is $k$ -connected if $κ (G) \geq k$ , and $k$ -edge-connected if $λ (G) \geq k$ .

These parameters obey Whitney's inequality:

κ (G) \leq λ (G) \leq δ (G)

⟳Removing all edges at a minimum-degree vertex

δ (G)

disconnects it, bounding

λ

; any vertex cut induces an edge cut of no greater size, bounding

κ \leq λ

Menger's Theorem (Vertex Form)

Let $u, v$ be non-adjacent vertices of a graph $G$ . The maximum number of internally vertex-disjoint $u$ – $v$ paths equals the minimum number of vertices (other than $u, v$ ) whose removal separates $u$ from $v$ .

In symbols, writing $p (u, v)$ for the max disjoint paths and $c (u, v)$ for the min vertex cut:

p (u, v) = c (u, v)

⟳Each path must use a distinct cut vertex (so

p \leq c

); the reverse uses an augmenting-path / max-flow argument to construct as many paths as the cut size.

A global corollary characterizes $k$ -connectivity:

κ (G) \geq k ⟺ every pair of vertices is joined by k internally disjoint paths

⟳Apply Menger to each pair; if every cut has size

\geq k

then by [3] every pair has

\geq k

disjoint paths, and conversely.

Why It Holds / Derivation

Menger's Theorem via Induction on Edges

We prove $p (u, v) = c (u, v)$ for non-adjacent $u, v$ .

Step 1 — Easy direction ( $p \leq c$ ). Any set of internally disjoint paths from

u

v

must each pass through the separating set

S

, and through distinct vertices of

S

(since the paths share no internal vertex). Hence the number of such paths is at most

∣ S ∣

, so

p (u, v) \leq c (u, v)

. Step 2 — Hard direction ( $p \geq c$ ), induction on $∣ E ∣$ . Let

k = c (u, v)

. We show

k

disjoint paths exist. Base case: no edges means

k = 0

, trivially satisfied. Step 3 — Pick an edge $e = x y$ . Consider

G - e

. If

c_{G - e} (u, v) \geq k

, induction gives

k

disjoint paths in

G - e \subseteq G

, done. Step 4 — Otherwise

c_{G - e} (u, v) = k - 1

, so there is a

(k - 1)

-vertex cut

T

G - e

. Adding back

e

, the sets

T \cup {x}

and

T \cup {y}

are each

u

–

v

cuts of size

k

G

(since

T

alone failed only because of

e

). Step 5 — Contract. Form

G_{1}

by contracting the "

u

-side" of the cut

T \cup {x}

, and

G_{2}

similarly. Each has fewer edges; by induction each yields

k

disjoint paths in its half. Splice the

k

paths through the cut vertices to obtain

k

disjoint

u

–

v

paths in

G

■

Karl Menger | 1902–1985

Austrian-American mathematician, member of the Vienna Circle, who proved his eponymous theorem in 1927 while studying curve theory and dimension. Menger's result was initially overlooked but later recognized as the combinatorial heart of duality theory — it is logically equivalent to König's theorem, Hall's marriage theorem, and the max-flow min-cut theorem. He also founded the field of distance geometry and contributed to the foundations of topology.

Building Intuition

Think of a graph as a city road map. A path is a route you could drive without revisiting any intersection. Connectivity asks: how many intersections (vertices) or roads (edges) would a saboteur have to close to cut downtown off from the airport? Menger says the saboteur's cheapest plan (smallest cut) exactly matches the number of completely independent routes you could simultaneously dispatch — neither side can beat the other. A tree is a road system with zero redundancy: removing any single road disconnects it. Adding one road back creates exactly one loop (cycle), which is your first taste of fault-tolerance.

Disjoint paths and a minimum vertex cut: three independent routes from u to v match the 3-vertex cut {a,b,c}.

Worked Examples

Connectivity of the Cube Graph $Q_3$

Given: The 3-cube

Q_{3}

has 8 vertices (binary strings

000

111

), edges joining strings differing in one bit. Every vertex has degree 3. Find:

κ (Q_{3})

and

λ (Q_{3})

. Steps:

Minimum degree $δ (Q_{3}) = 3$ , so by [2], $κ \leq λ \leq 3$ .
To show $λ \geq 3$ : $Q_{3}$ is vertex-transitive and 3-regular; no single or double edge removal disconnects it (checking: removing 2 edges leaves every vertex with degree $\geq 1$ and the graph stays connected by exhaustive structure).
To show $κ \geq 3$ : between any two vertices one can route 3 internally disjoint paths (e.g., from $000$ to $111$ , flip bits in the three different orders).
Therefore $κ = λ = 3$ .

Answer:

κ (Q_{3}) = λ (Q_{3}) = 3

— the hypercube is maximally connected for its degree.

Counting Disjoint Paths via a Cut

Given: A graph

G

in which the minimum

u

–

v

vertex cut is

S = {a, b, c}

∣ S ∣ = 3

, and

u, v

are non-adjacent. Find: The maximum number of internally vertex-disjoint

u

–

v

paths. Steps:

By Menger's theorem [3], $p (u, v) = c (u, v)$ .
The minimum cut has size 3, so $c (u, v) = 3$ .
Therefore $p (u, v) = 3$ — and we can constructively route one path through each of $a$ , $b$ , $c$ .
No 4th disjoint path exists: a 4th would need an internal vertex outside $S$ on a route avoiding $S$ , contradicting that $S$ separates $u$ from $v$ .

Answer:

p (u, v) = 3

internally disjoint paths, exactly matching the cut.

Common Misconceptions

"Path = walk = trail." These are distinct. A walk may repeat vertices and edges; a trail forbids repeated edges but allows repeated vertices; a path forbids repeated vertices entirely. Eulerian circuits are trails (use every edge once); Hamiltonian cycles are paths/cycles (visit every vertex once). Confusing them produces false theorems. " $κ = λ$ always." False in general. Inequality [2] can be strict. Consider two triangles sharing a single vertex (a "bowtie"):

κ = 1

(remove the central cut vertex) but

λ = 2

(you must cut two edges to disconnect). Equality holds for many regular graphs but is not automatic.

Edge-connectivity exceeds vertex-connectivity

Take graph $G$ formed by two complete graphs $K_{4}$ sharing exactly one common vertex $w$ .

Removing the single vertex $w$ splits $G$ into two components, so $κ (G) = 1$ .
But $w$ has degree 6, and every other vertex has degree 3; to disconnect by edges you must isolate some $K_{4}$ , requiring removal of at least 2 edges. Careful inspection gives $λ (G) = 3$ (matching $δ = 3$ ).

Thus $κ (G) = 1 < λ (G) = 3$ , a strict instance of Whitney's inequality [2].

Connections

Connectivity sits at a crossroads of graph theory. Menger's theorem [3] is the combinatorial twin of the Max-Flow Min-Cut Theorem — set every edge capacity to 1 and the max flow equals the max number of edge-disjoint paths. Cycles connect to Trees and Spanning Trees: a connected graph is a tree iff it has $n - 1$ edges and no cycle, and the cycle space has dimension $∣ E ∣ - ∣ V ∣ + c$ (the cyclomatic number). The study of paths feeds directly into Shortest Path Algorithms (Dijkstra, BFS) and Eulerian and Hamiltonian Graphs. Higher connectivity governs Planar Graphs (3-connected planar graphs have unique embeddings, by Whitney).

Real-World Applications

Internet/network reliability — $k$ -connectivity guarantees a network survives $k - 1$ node failures; backbone designers enforce $κ \geq 2$ for redundancy.
Telecommunications routing — edge-disjoint paths (via Menger) let you send data over independent channels for fault tolerance and load balancing.
Transportation planning — identifying cut vertices (articulation points) reveals critical intersections or bridges whose failure isolates regions.
VLSI circuit layout — connectivity ensures all components share a common ground; disjoint-path routing avoids signal interference.
Power grid resilience — minimum cuts identify the smallest set of transmission lines whose failure causes a blackout cascade.
Social network analysis — components and connectivity measure community cohesion and the spread potential of information.
Bioinformatics — protein–protein interaction networks use connectivity to find essential genes (high-betweenness cut vertices).

Historical Development

1736 — Leonhard Euler solves the Königsberg Bridges problem, founding graph theory and the study of trails/circuits.
1857 — Arthur Cayley counts labelled trees, formalizing connected acyclic graphs.
1873 — Carl Hierholzer characterizes Eulerian circuits (every vertex even degree, connected).
1927 — Karl Menger proves his min-max theorem on disjoint paths and separating sets.
1931 — Dénes König establishes his theorem for bipartite graphs, later seen equivalent to Menger.
1932 — Hassler Whitney introduces vertex/edge connectivity and proves $κ \leq λ \leq δ$ ; he also relates 3-connectivity to unique planar embeddings.
1956 — Ford and Fulkerson prove the Max-Flow Min-Cut theorem, generalizing Menger to capacitated networks.
1961 — W. T. Tutte develops deeper structural connectivity theory (the wheel theorem for 3-connected graphs).
1973 — Hopcroft and Tarjan give a linear-time algorithm to find biconnected components and articulation points.

Subtleties & Limits

While 2-connectivity and 3-connectivity are algorithmically well understood (linear and near-linear time), the structure of $k$ -connected graphs for large $k$ remains subtle. The exact relationship between connectivity and the existence of specific spanning substructures is the subject of major conjectures. For example, Lovász's conjecture on connectivity and tough paths, and questions about how linkage (routing prescribed terminal pairs along disjoint paths) scales — the $k$ -disjoint-paths problem is polynomial for fixed $k$ (Robertson–Seymour) but the dependence on $k$ is towering. The interplay between high connectivity and the forced appearance of large minors and subdivisions continues to drive structural graph theory.