Graph Theory37 sections · 1633 units
Open in Course

Max-Flow Min-Cut Theorem

(Duality result)

The theorem states: the maximum flow value equals the minimum cut capacity. Proof sketch: the flow is at most the capacity of any cut (flow must cross every cut). When the algorithm terminates, the flow equals the capacity of some cut (the min-cut).

This means max flow and min-cut are two views of the same problem. Solving one solves the other. The theorem is both beautiful and useful for proving correctness.