I'm about to read the proof of the max-flow min-cut theorem that helps solve the maximum network flow problem. Could someone please suggest an intuitive way to understand the theorem?

  • $\begingroup$ Max-flow min-cut is part of a family of theorems all of which assert that some obvious necessary condition is in fact sufficient, and all of which are somehow equivalent. It is worth studying all of these theorems as well as proofs of their equivalences to get a feel for the underlying result: en.wikipedia.org/wiki/… $\endgroup$ – Qiaochu Yuan Jun 22 '12 at 22:35

Imagine a complex pipeline with a common source and common sink. You start to pump the water up, but you can't exceed some maximum flow. Why is that? Because there is some kind of bottleneck, i.e. a subset of pipes that transfer the fluid at their maximum capacity--you can't push more through. This bottleneck will be precisely the minimum cut, i.e. the set of edges that block the flow. Please note, that there may be more that one minimum cut. If you find one, the you know the maximum flow; knowing the maximum flow you know the capacity of the cut.

Hope that explains something ;-)


A cut is a bottleneck: any total flow through the network must all pass through the bottleneck at once.

The bottle might have a wide part and a narrow part. The total flow must pass through the wide part and the narrow part. It is limited by the narrow part, not by the wide part, because the wide part is wide and can accommodate the flow into or out of the narrow part.

Overall, total flow through the bottle will be constrained by the total flow that can pass through the narrowest bottleneck.

So to find the maximum possible flow, you find the narrowest bottleneck in the bottle, which is the minimum cut.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.