Lesson 5

Menger's Theorem is an example of a strong duality result. Weak duality, stating that the minimum of one function is greater than or equal to the maximum of the other, is easy to verify: let \(m\) be the maximum number of vertex-disjoint (respectively, edge-disjoint) paths from \(s\) to \(t\). Then it is impossible to separate \(s\) and \(t\) by removing fewer than \(m\) vertices (respectively, edges), since something must be removed from each of the \(m\) paths. And strong duality asserts that the minimum and maximum coincide. We will derive Menger's Theorem from the Ford–Fulkerson Theorem, which can be viewed as a generalization of Menger's Theorem to weighted graphs. The Ford–Fulkerson Theorem itself is a special case of the strong duality of linear programming, where one seeks the optimum of a linear function under linear constraints on the variables.