Menger's Theorem

Max internally disjoint paths equals min vertex cut.

The idea

Theorem (Menger's theorem).

Let $u$ and $v$ be distinct, non-adjacent vertices of a graph. The maximum number of $u\,v$-paths that pairwise share no vertex other than $u$ and $v$ equals the minimum number of vertices, other than $u$ and $v$, whose deletion leaves no $u\,v$-path: $\max\{\text{internally disjoint } u\,v\text{-paths}\} = \min\{|S| : S \text{ separates } u \text{ from } v\}.$

The terms: a $u\,v$-path runs from $u$ to $v$ along edges without repeating a vertex, and its internal vertices are all of its vertices except $u$ and $v$ themselves. Two $u\,v$-paths are internally disjoint when they share no internal vertex, so they may meet only at the two ends. A set $S$ of vertices containing neither $u$ nor $v$ separates $u$ from $v$ if deleting the vertices of $S$ leaves no $u\,v$-path; such an $S$ is a $u\,v$-separator.

One of the two inequalities is easy, and the theorem is its converse: the largest family of internally disjoint paths is exactly as large as the smallest separator. Exhibiting one small separator therefore proves that no larger family of disjoint paths exists.

Ways to work on it

• Walkthrough. The path-cut duality: disjoint paths, separators, and k-connectivity.
• Practice. Convert between a min separator and the max disjoint-path count.
• Hardest. Pin down the vertex connectivity of a graph exactly.

Not sure where to start? Take the ten-question placement test.