Menger's Theorem

Theorem7.2Menger's Theorem (Edge and Vertex Versions)

Edge version: For non-adjacent vertices $s, t$ in a graph $G$ , the maximum number of edge-disjoint $s$ - $t$ paths equals the minimum size of an $s$ - $t$ edge cut (minimum number of edges whose removal disconnects $s$ from $t$ ).

Vertex version: For non-adjacent vertices $s, t$ in a graph $G$ , the maximum number of internally vertex-disjoint $s$ - $t$ paths equals the minimum size of an $s$ - $t$ vertex separator (minimum number of vertices, excluding $s$ and $t$ , whose removal disconnects $s$ from $t$ ).

Proof

Edge version (from max-flow min-cut). Direct each edge of $G$ as two antiparallel arcs, each with capacity 1. The max $s$ - $t$ flow equals the max number of edge-disjoint paths (by flow decomposition and integrality). The min cut in this network corresponds to a minimum edge cut in $G$ . By max-flow min-cut: max edge-disjoint paths = min edge cut.

Vertex version (by vertex splitting). Create a directed graph $G'$ : replace each vertex $v \notin \{s,t\}$ by two copies $v_{\text{in}}$ and $v_{\text{out}}$ connected by arc $(v_{\text{in}}, v_{\text{out}})$ of capacity 1. Each original edge $uv$ becomes arcs $(u_{\text{out}}, v_{\text{in}})$ and $(v_{\text{out}}, u_{\text{in}})$ of capacity $\infty$ (or $n$ ). Keep $s = s_{\text{out}}$ and $t = t_{\text{in}}$ .

In $G'$ : flow through vertex $v$ in the original graph is limited to 1 by the arc $(v_{\text{in}}, v_{\text{out}})$ . An integer max flow of value $k$ decomposes into $k$ paths that are internally vertex-disjoint in $G$ (since each vertex arc has capacity 1).

A minimum cut in $G'$ : cutting vertex arcs $(v_{\text{in}}, v_{\text{out}})$ corresponds to a vertex separator in $G$ (since cutting the $\infty$ -capacity edges is never optimal). The min cut capacity equals the min vertex separator size.

By max-flow min-cut in $G'$ : max vertex-disjoint paths = min vertex separator. $\square$

■

ExampleMenger and Connectivity

Whitney's theorem: $G$ is $k$ -connected (i.e., $\kappa(G) \geq k$ ) if and only if every pair of vertices has $k$ internally vertex-disjoint paths. Proof: by Menger's theorem, $k$ vertex-disjoint paths exist iff every vertex separator has size $\geq k$ , which is the definition of $k$ -connectivity. Similarly, $G$ is $k$ -edge-connected iff every pair has $k$ edge-disjoint paths.

RemarkGlobal Connectivity

Computing the edge connectivity $\lambda(G) = \min_{s,t} \lambda(s,t)$ requires $O(n)$ max-flow computations (fix $s$ , compute max-flow to each $t$ , take minimum). The Stoer-Wagner algorithm computes $\lambda(G)$ for undirected graphs in $O(nm + n^2\log n)$ without max-flow, using minimum cut phases based on maximum adjacency ordering.