Menger's Theorem

The question

Here is the prism from module 15 again: the outer triangle $0,1,2$, the inner triangle $3,4,5$, and the rungs $0$–$3$, $1$–$4$, $2$–$5$.

How many routes from router $0$ to router $4$ can you find that share no router in between? The picture shows three. Could there be four? No: router $0$ has only three neighbors, and every route leaves $0$ through one of them. So deleting the three routers $1,2,3$ cuts $0$ off from $4$, and that set of three is a certificate that no fourth route exists.

So here two numbers coincide: the most routes that avoid each other, and the fewest routers whose removal separates $0$ from $4$. Menger's theorem says they always coincide. It is the connectivity version of module 11's matching–cover pair: two certificates of the same size that prove each other optimal.

The naive approach, and where it wastes work

from itertools import combinations
from collections import deque

def network(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, set()).add(v)
        g.setdefault(v, set()).add(u)
    return g

def reachable(g, x, y, removed=()):
    gone, seen, queue = set(removed), {x}, deque([x])
    while queue:
        u = queue.popleft()
        for w in g[u]:
            if w not in gone and w not in seen:
                seen.add(w)
                queue.append(w)
    return y in seen

def min_cut(g, x, y):
    """Fewest vertices other than x, y whose deletion separates them (brute force)."""
    others = [v for v in g if v not in (x, y)]
    return next(k for k in range(len(others) + 1)
                for S in combinations(others, k) if not reachable(g, x, y, S))

prism = network([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (0, 3), (1, 4), (2, 5)])
assert 4 not in prism[0] and min_cut(prism, 0, 4) == 3

Searching every set of routers doubles the work with each router added, and its answer, "the minimum is 3", is only believable if you rerun it. Three explicit routes and three explicit routers are believable at a glance. The theorem promises both always exist.

Cuts and disjoint paths

Let $x$ and $y$ be non-adjacent vertices of a graph $G$. An $x,y$-cut is a set $S$ of vertices, not containing $x$ or $y$, such that $G-S$ has no $x,y$-path. Write $\kappa (x,y)$ for the minimum size of an $x,y$-cut, and $\lambda (x,y)$ for the maximum number of pairwise internally disjoint $x,y$-paths (paths sharing no vertex other than $x$ and $y$).

One inequality is easy: $\lambda (x,y)\le \kappa (x,y)$. Every $x,y$-cut contains an internal vertex of each of the paths, and since the paths are internally disjoint, these vertices are distinct.

The requirement that $x$ and $y$ be non-adjacent matters: if $xy$ is an edge, no set of other vertices can separate them, and the path $x,y$ has no internal vertex at all.

Menger's theorem

Proof. We have $\lambda \le \kappa$. For $\kappa \le \lambda$ we show, by induction on the number of vertices, that there are $k=\kappa (x,y)$ internally disjoint $x,y$-paths. If $k=0$ there is nothing to show, so let $k\ge 1$.

Case 1: some minimum $x,y$-cut $S$ is neither $N(x)$ nor $N(y)$. Call a path from $x$ that meets $S$ only at its last vertex an $x,S$-path, and define $y,S$-paths the same way. Let $V_1$ be the set of vertices on $x,S$-paths and $V_2$ the set of vertices on $y,S$-paths.

• $V_1\cap V_2=S$. Each $s\in S$ is in both: since $S$ is a minimum cut, $S-\{s\}$ is not a cut, so some $x,y$-path meets $S$ only at $s$, and its two halves are an $x,S$-path and a $y,S$-path ending at $s$. A vertex outside $S$ in both sets would give a walk from $x$ to $y$ that avoids $S$. For the same reason $y\notin V_1$ and $x\notin V_2$.
• Build $H_1$ from $G[V_1]$ by adding a new vertex $y^{\prime }$ adjacent to every vertex of $S$, and $H_2$ from $G[V_2]$ by adding $x^{\prime }$ adjacent to $S$. Every $x,y^{\prime }$-cut of $H_1$ is an $x,y$-cut of $G$: an $x,y$-path of $G$ avoiding it would reach $S$, and its part up to its first vertex of $S$ is an $x,S$-path, which lies in $H_1$. So ${\kappa }_{H_1}(x,y^{\prime })\ge k$, and likewise for $H_2$.
• $H_1$ has fewer vertices than $G$: it adds only $y^{\prime }$, and $G$ has at least two vertices outside $V_1$. One is $y$. For a second: if some $s\in S$ is not adjacent to $y$, an $x,y$-path meeting $S$ only at $s$ has a vertex strictly between $s$ and $y$, on a $y,S$-path and outside $S$, so not in $V_1$. Otherwise $S\subseteq N(y)$, and since $S\ne N(y)$, $y$ has a neighbor outside $S$, which is not in $V_1$ either (it would give an $x,y$-path avoiding $S$). Similarly for $H_2$, using $S\ne N(x)$.

By induction $H_1$ has $k$ internally disjoint $x,y^{\prime }$-paths. Their vertices just before $y^{\prime }$ are $k$ distinct vertices of $S$, so they are all of $S$, and no path contains a second vertex of $S$ (it would share that vertex with another path). Dropping $y^{\prime }$ leaves $k$ $x,S$-paths ending at distinct vertices of $S$. In the same way $H_2$ gives $k$ $y,S$-paths. Joining the two paths that end at each $s\in S$ gives $k$ $x,y$-paths in $G$, internally disjoint because the $x$-halves lie in $V_1$, the $y$-halves in $V_2$, and $V_1\cap V_2=S$, with each vertex of $S$ used once.

Case 2: every minimum $x,y$-cut is $N(x)$ or $N(y)$.

• If some vertex $v$ is neither $x$, $y$, nor a neighbor of either, delete it. If $G-v$ had an $x,y$-cut $T$ with fewer than $k$ vertices, then $T\cup \{v\}$ would be an $x,y$-cut of $G$ with at most $k$ vertices, hence a minimum one, and it contains $v$, so it is neither $N(x)$ nor $N(y)$, contradicting the case. Hence ${\kappa }_{G-v}(x,y)=k$, and induction gives $k$ paths.
• If some $v$ is adjacent to both $x$ and $y$, it lies in every $x,y$-cut, so ${\kappa }_{G-v}(x,y)=k-1$. Induction gives $k-1$ paths in $G-v$; add the path $x,v,y$.
• Otherwise $N(x)$ and $N(y)$ split the other vertices. Let $B$ be the bipartite graph of edges of $G$ between $N(x)$ and $N(y)$. A set of other vertices is an $x,y$-cut exactly when it covers every edge of $B$: an uncovered edge $uv$ gives the path $x,u,v,y$, and every $x,y$-path must cross from $N(x)$ to $N(y)$ along an edge of $B$. So the minimum vertex cover of $B$ has size $k$, and by König–Egerváry (module 11) $B$ has a matching of $k$ edges $u_i{v}_i$. The paths $x,u_i,v_i,y$ are internally disjoint. $◻$

Proof moves used here.

• Induction on the number of vertices, with the cases arranged so the smaller graphs really are smaller.
• Decomposition: in Case 1, cut the graph at a minimum cut, solve each side, and glue.
• Certificate pair: the base case is König–Egerváry, the matching–cover duality of module 11.
• Case split on how the minimum cuts sit, so every situation is covered once.

Traced on the prism

For $x=0$ and $y=4$ the neighborhood $N(0)=\{1,2,3\}$ is a minimum cut, and so is $N(4)=\{1,3,5\}$, and there is no other, so the proof runs Case 2. The vertices 1 and 3 are common neighbors: the proof deletes 1, finds two paths in what remains (deleting 3 the same way leaves the single path $0,2,5,4$), and adds back $0,1,4$ and $0,3,4$. The three routes in the picture are the result:

paths = [[0, 1, 4], [0, 3, 4], [0, 2, 5, 4]]
assert all(all(b in prism[a] for a, b in zip(p, p[1:])) for p in paths)
inner = [set(p[1:-1]) for p in paths]
assert all(not inner[i] & inner[j] for i in range(3) for j in range(i + 1, 3))
assert len(paths) == min_cut(prism, 0, 4) == 3

Every pair: the global version

Theorem. A graph $G$ with at least $k+1$ vertices is $k$-connected if and only if every two vertices of $G$ are joined by $k$ pairwise internally disjoint paths.

Proof. If. Deleting fewer than $k$ vertices leaves at least one of the $k$ paths between any two remaining vertices intact, so the rest stays connected.

Only if. Let $G$ be $k$-connected and $x,y$ two vertices. If they are non-adjacent, every $x,y$-cut is a separating set, so $\kappa (x,y)\ge k$, and Menger gives $k$ paths. If $xy$ is an edge, look at $G^{\prime }=G-xy$, where $x$ and $y$ are non-adjacent. Let $S$ be an $x,y$-cut of $G^{\prime }$; we show $|S|\ge k-1$. Suppose $|S|\le k-2$. In $G^{\prime }-S$, let $A$ be the component of $x$ and $B$ the component of $y$. Since $G-S$ is connected ($|S|<k$), the edge $xy$ is the only link between $A$ and $B$, and every other vertex lies in $A$ or $B$. There is such a vertex, because $n\ge k+1>|S|+2$. If some $z\ne x$ is in $A$, then $S\cup \{x\}$ separates $z$ from $y$ in $G$, a separating set of at most $k-1$ vertices; if some $z\ne y$ is in $B$, use $S\cup \{y\}$. Either way $G$ is not $k$-connected, a contradiction. So ${\kappa }_{G^{\prime }}(x,y)\ge k-1$, Menger gives $k-1$ internally disjoint paths in $G^{\prime }$, and the edge $xy$ is the $k$-th. $◻$

Proof move used here. Quantifiers matter: the local theorem is about one pair; the global one needs the local one for every pair, including the adjacent ones, which need their own argument.

Cutting edges instead: the edge version

The same holds for edges. For distinct vertices $x,y$, the minimum number of edges whose deletion separates them equals the maximum number of pairwise edge-disjoint $x,y$-paths. One way to see it: attach new vertices $s$ to $x$ and $t$ to $y$, and apply the vertex version to the line graph, whose vertices are the edges of $G+sx+ty$; edge-disjoint paths and edge cuts of $G$ become internally disjoint paths and vertex cuts there. We sketch this and do not prove it here; module 17 proves the edge version again with flows. As before, $G$ is $k$-edge-connected exactly when every two vertices are joined by $k$ edge-disjoint paths.

The Fan Lemma

A tool that the next modules use often:

Fan Lemma. If $G$ is $k$-connected, $x$ is a vertex, and $U$ is a set of at least $k$ vertices not containing $x$, then there are $k$ paths from $x$ to distinct vertices of $U$ that share only the vertex $x$ (a fan).

You will prove it in the lab, from Menger's theorem.

What a certificate costs

$k$ internally disjoint paths and an $x,y$-cut of size $k$ are each checked in $O(n+m)$ time, and together they prove $\kappa (x,y)=k$. Searching every set of vertices costs up to $2^{n-2}$ reachability tests. Finding a family and a cut together needs no such search: the lab's first exercise grows both with about $\mathrm{deg}(x)$ reachability searches, and module 17's flows extend the idea.

A problem that looks different

In a city, the town hall stands at one end and the train station at the other. Engineers ask how many streets must close before no route between them remains, and how many routes can be kept open at once without sharing a street. Then they ask the same about every pair of buildings in the city at once. Nothing in the question mentions cuts or disjoint paths. The lab's last exercise is another question like that.

Practise

The lab runs in your browser. Your code grows a family of routes that share no street and reads off a cut of the same size, then finds routes that share no router with a tool built only for streets. Half of the lab is proofs: assemble the proof of the Fan Lemma, find the false step in an argument about connectivity, and write a proof for a problem that names no technique.

Recap

• You can now: define $\kappa (x,y)$ and $\lambda (x,y)$; prove $\lambda \le \kappa$; prove Menger's theorem by induction, with König–Egerváry as the base case; prove the global version, including adjacent pairs; and state the edge version and the Fan Lemma.
• Invariant: every $x,y$-cut meets each of a family of internally disjoint paths in a different vertex, so a family of $k$ paths and a cut of size $k$ prove each other optimal.
• Complexity achieved: both certificates are checked in $O(n+m)$, against up to $2^{n-2}$ vertex sets for a brute-force minimum cut.
• Failure mode: treating $k$ disjoint paths between one pair as proof that the whole graph is $k$-connected; and forgetting that adjacent vertices have no vertex cut.
• In real software: NetworkX's node_disjoint_paths and edge_disjoint_paths find disjoint paths with maximum-flow computations, and minimum_node_cut returns the matching cut.
• Retrieval: module 14 bounded $\kappa (G)$ above by an explicit separating set. What is the matching lower-bound certificate? (For every pair of vertices, $k$ internally disjoint paths.)

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

1. In Case 1, why does $S\ne N(y)$ guarantee that $H_1$ is smaller than $G$?
2. Why does the base case need König–Egerváry, and where exactly do the bipartite graph's vertex covers come from?
3. In the global version, why does an adjacent pair need a separate argument, and where is $n\ge k+1$ used?

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.