Graph Theory37 sections · 1633 units
Open in Course

Max-Flow Min-Cut Theorem

(Flow equals cut capacity)

The max-flow min-cut theorem states: the maximum flow from ss to tt equals the capacity of the minimum ss-tt cut. This is one of the most beautiful results in graph theory. Why?

The flow cannot exceed any cut capacity (flow conservation). The minimum cut is the tightest bottleneck. When max flow is reached, it saturates this cut. No more flow can squeeze through. This theorem connects two seemingly different problems: finding maximum flow and finding minimum cuts. Solve one, you have solved the other.