Lesson 3

Theorem (Ford–Fulkerson, 1962). The size of the maximum flow in a network equals the capacity of the minimum \((s,t)\)-cut.

Proof. Consider a maximum flow \(f\) and its corresponding residual network \(G^{f}\). In the network \(G^{f}\), vertex \(t\) is not reachable from \(s\) (otherwise the flow could be increased). Let \(L\) be the set of vertices reachable from \(s\) in the residual network \(G^{f}\), and let \(R\) be the rest: \(R = V-L\).

We claim that \[\operatorname{size}(f) = \operatorname{capacity}(L,R).\] Indeed, since there are no edges from \(L\) to \(R\) in the residual network, our flow fully saturates the edges from \(L\) to \(R\) in the original network and does not use edges from \(R\) to \(L\): in the diagram \(f(e) = c(e)\) and \(f(e') = 0\). Thus, the flow in the network (which can be controlled at the customs border between \(L\) and \(R\)) exactly equals the cut capacity.◼