Lesson 7

Proof. [Proof of Menger's Theorem] We construct a set of vertex- (edge-) disjoint \((s,t)\)-paths \(P\) and a set of vertices (edges) \(Y\), whose removal leaves no \((s,t)\)-paths. It suffices to show that \[|P| \ge |Y|\] Indeed, \[\max_{P}|P| \le \min_{Y}|Y| \ ,\] so if we find objects with \(|P| \ge |Y|\), then maximum and minimum above are equal.

1. Start with the edge version of the theorem for directed graphs. Let \(P\) be a maximum-size set of edge-disjoint paths from \(s\) to \(t\). By the just-proven lemma, there is an \((s,t)\)-flow of size \(|P|\), and by the Ford–Fulkerson Theorem, there is also an \((s,t)\)-cut of size \(|P|\). Let \(Y\) be all the edges of this cut: their removal separates vertices \(s\) and \(t\). Thus, we constructed \(P\) and \(Y\) such that \(|P|=\operatorname{size}(f)=|Y|\).
2. The edge version for undirected graphs is obtained by reducing to directed graphs. Namely, we transform an undirected graph into a network by replacing each edge \(\{u,v\}\) with two edges \((u,v)\) and \((v,u)\). As in the previous step, we construct \(P\) and \(Y\) with \(|P|=\operatorname{size}(f)=|Y|\). There’s a subtle technical point: the found paths in \(P\) are edge-disjoint in the network, but may intersect in the original undirected graph if one path uses edge \((u,v)\) and another uses \((v,u)\). To avoid this, we should “clean” the maximum flow \(f\) beforehand: zero out the flow on all such \(u \to v \to u\) cycles.
3. The vertex version reduces to the edge one as follows. Take a network \(G\) and split each vertex \(v \ne s,t\) as follows:

   

   Call the resulting graph (and corresponding network) \(G'\). Let \(P\) be the maximum-size set of vertex- disjoint \((s,t)\)-paths in \(G\), and \(P'\) be the maximum-size set of edge- disjoint \((s,t)\)-paths in \(G'\). It’s easy to see that \(|P| \ge |P'|\): if the paths are edge-disjoint in \(G'\), then they are vertex-disjoint in \(G\). We already know that in \(G'\) there is a set of edges \(Y'\), whose removal separates \(s\) and \(t\), such that \(|Y'|=|P'|\). Let \(Y\) be a minimum-size set of vertices to remove in \(G\) to separate \(s\) and \(t\). Note that \(|Y'| \ge |Y|\): in each edge from \(Y'\), we can remove one endpoint, distinct from \(s\) and \(t\), in \(G\). Hence, \[|P| \ge |P'|=|Y'| \ge |Y| \ .\]