Two views of the same number
A cut splits the nodes into a side with the source and a side with the sink. The capacity of a cut is the total capacity of edges crossing from the source side to the sink side. The famous theorem says the maximum flow equals the minimum cut capacity.
Why they match
Any flow must cross every cut, so no flow can exceed the smallest cut capacity. That gives an upper bound. The deeper direction shows the bound is tight:
- Run a maximum flow until no augmenting path remains.
- Mark every node still reachable from the source in the residual graph.
- Edges from marked to unmarked nodes are full and form a cut whose capacity equals the flow.
So the flow value and a cut value meet exactly, proving both are optimal.
Why it matters
The theorem turns optimization into structure: finding the most flow also reveals the cheapest set of edges whose removal separates source from sink. This duality underlies image segmentation, reliability analysis, and project selection.
Key idea
Maximum flow equals minimum cut, and the saturated edges leaving the source reachable set reveal that cheapest separating cut.