Proof sketch
Max flow ≤ min cut (any flow crossing any cut). Ford-Fulkerson termination proves converse — residual graph is disconnected at max flow → cut of that value exists.
Advertisement
Finding min cut
Run max-flow. In residual graph, vertices reachable from s = S side. Rest = T. Edges from S to T (in original) = min cut.
Advertisement
Applications
Bipartite matching (König). Image segmentation. Project selection. Any 'min separator'.
Multi-commodity
Max-flow min-cut fails for multi-commodity flow with different commodities. Only approximate duality.