Graph Theory — Paths, Cycles, Connectivity

⚡ Key Takeaways

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).

💡 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

DefinitionWalks, Trails, Paths, Cycles

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

  • A walk of length kk is an alternating sequence v0e1v1e2⋯ekvkv_0 e_1 v_1 e_2 \cdots e_k v_k where each edge eie_i joins vi−1v_{i-1} and viv_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 v0=vkv_0 = v_k.
  • A cycle is a closed walk of length ≥3\geq 3 with no repeated vertex except v0=vkv_0 = v_k.

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

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

1
ℓ(P)=∣E(P)∣=∣V(P)∣−1\quad \ell(P) = |E(P)| = |V(P)| - 1

Derivation hint: A path visits n+1n+1 distinct vertices in sequence; consecutive pairs define edges, giving one fewer edge than vertices.

DefinitionConnectivity

A graph GG is connected if for every pair u,v∈Vu, v \in V there exists a uu–vv path. A maximal connected subgraph is a connected component. The vertex connectivity κ(G)\kappa(G) is the minimum number of vertices whose removal disconnects GG (or reduces it to a single vertex). The edge connectivity λ(G)\lambda(G) is the minimum number of edges whose removal disconnects GG. A graph is kk-connected if κ(G)≥k\kappa(G) \geq k, and kk-edge-connected if λ(G)≥k\lambda(G) \geq k.

These parameters obey Whitney's inequality:

2
κ(G)≤λ(G)≤δ(G)\quad \kappa(G) \leq \lambda(G) \leq \delta(G)

Derivation hint: Removing all edges at a minimum-degree vertex δ(G)\delta(G) disconnects it, bounding λ\lambda; any vertex cut induces an edge cut of no greater size, bounding κ≤λ\kappa \leq \lambda.

TheoremMenger's Theorem (Vertex Form)

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

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

3
p(u,v)=c(u,v)\quad p(u,v) = c(u,v)

Derivation hint: Each path must use a distinct cut vertex (so p≤cp \leq c); the reverse uses an augmenting-path / max-flow argument to construct as many paths as the cut size. A global corollary characterizes kk-connectivity:

4
κ(G)≥k  ⟺  every pair of vertices is joined by k internally disjoint paths\quad \kappa(G) \geq k \iff \text{every pair of vertices is joined by } k \text{ internally disjoint paths}

Derivation hint: Apply Menger to each pair; if every cut has size ≥k\geq k then by [3] every pair has ≥k\geq k disjoint paths, and conversely.

Why It Holds / Derivation

ProofMenger's Theorem via Induction on Edges

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

Step 1 — Easy direction (p≤cp \leq c). Any set of internally disjoint paths from uu to vv must each pass through the separating set SS, and through distinct vertices of SS (since the paths share no internal vertex). Hence the number of such paths is at most ∣S∣|S|, so p(u,v)≤c(u,v)p(u,v) \leq c(u,v).

Step 2 — Hard direction (p≥cp \geq c), induction on ∣E∣|E|. Let k=c(u,v)k = c(u,v). We show kk disjoint paths exist. Base case: no edges means k=0k = 0, trivially satisfied.

Step 3 — Pick an edge e=xye = xy. Consider G−eG - e. If cG−e(u,v)≥kc_{G-e}(u,v) \geq k, induction gives kk disjoint paths in G−e⊆GG - e \subseteq G, done.

Step 4 — Otherwise cG−e(u,v)=k−1c_{G-e}(u,v) = k - 1, so there is a (k−1)(k-1)-vertex cut TT in G−eG - e. Adding back ee, the sets T∪{x}T \cup \{x\} and T∪{y}T \cup \{y\} are each uu–vv cuts of size kk in GG (since TT alone failed only because of ee).

Step 5 — Contract. Form G1G_1 by contracting the "uu-side" of the cut T∪{x}T \cup \{x\}, and G2G_2 similarly. Each has fewer edges; by induction each yields kk disjoint paths in its half. Splice the kk paths through the cut vertices to obtain kk disjoint uu–vv paths in GG. ■\blacksquare

∎
mathematician · 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

🧠 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.

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

Worked Examples

ExampleConnectivity of the Cube Graph Q3Q_3

Given: The 3-cube Q3Q_3 has 8 vertices (binary strings 000000 to 111111), edges joining strings differing in one bit. Every vertex has degree 3.

Find: κ(Q3)\kappa(Q_3) and λ(Q3)\lambda(Q_3).

Steps: 1. Minimum degree δ(Q3)=3\delta(Q_3) = 3, so by [2], κ≤λ≤3\kappa \leq \lambda \leq 3. 2. To show λ≥3\lambda \geq 3: Q3Q_3 is vertex-transitive and 3-regular; no single or double edge removal disconnects it (checking: removing 2 edges leaves every vertex with degree ≥1\geq 1 and the graph stays connected by exhaustive structure). 3. To show κ≥3\kappa \geq 3: between any two vertices one can route 3 internally disjoint paths (e.g., from 000000 to 111111, flip bits in the three different orders). 4. Therefore κ=λ=3\kappa = \lambda = 3.

Answer: κ(Q3)=λ(Q3)=3\boxed{\kappa(Q_3) = \lambda(Q_3) = 3} — the hypercube is maximally connected for its degree.

ExampleCounting Disjoint Paths via a Cut

Given: A graph GG in which the minimum uu–vv vertex cut is S={a,b,c}S = \{a, b, c\}, ∣S∣=3|S| = 3, and u,vu, v are non-adjacent.

Find: The maximum number of internally vertex-disjoint uu–vv paths.

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

Answer: p(u,v)=3\boxed{p(u,v) = 3} internally disjoint paths, exactly matching the cut.

Common Misconceptions

⚠️ Common mistake

"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.

⚠️ Common mistake

"κ=λ\kappa = \lambda always." False in general. Inequality [2] can be strict. Consider two triangles sharing a single vertex (a "bowtie"): κ=1\kappa = 1 (remove the central cut vertex) but λ=2\lambda = 2 (you must cut two edges to disconnect). Equality holds for many regular graphs but is not automatic.

CounterexampleEdge-connectivity exceeds vertex-connectivity

Take graph GG formed by two complete graphs K4K_4 sharing exactly one common vertex ww.

  • Removing the single vertex ww splits GG into two components, so κ(G)=1\kappa(G) = 1.
  • But ww has degree 6, and every other vertex has degree 3; to disconnect by edges you must isolate some K4K_4, requiring removal of at least 2 edges. Careful inspection gives λ(G)=3\lambda(G) = 3 (matching δ=3\delta = 3).

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

Connections

connection

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−1n-1 edges and no cycle, and the cycle space has dimension ∣E∣−∣V∣+c|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

🔬 Where this appears

Historical Development

⏳ History
- 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 κ≤λ≤δ\kappa \leq \lambda \leq \delta; 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

open-problem

While 2-connectivity and 3-connectivity are algorithmically well understood (linear and near-linear time), the structure of kk-connected graphs for large kk 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 kk-disjoint-paths problem is polynomial for fixed kk (Robertson–Seymour) but the dependence on kk is towering. The interplay between high connectivity and the forced appearance of large minors and subdivisions continues to drive structural graph theory.

See Also

Max-Flow Min-Cut Theorem · Trees and Spanning Trees · Shortest Path Algorithms · Eulerian and Hamiltonian Graphs · Planar Graphs · Matching Theory · Graph Theory Fundamentals