Maximum flow and minimum cut

Why does the most a network can carry equal the cheapest way to cut it in two?

Take a network of pipes, or roads, or cables, with a source at one end and a destination at the other, and a capacity on every link. Two questions suggest themselves. How much can flow from source to destination at once? And what is the cheapest set of links to sever so that nothing can get through at all?

One is a question about sending, the other about breaking. They are asked by different people for opposite reasons. Yet the answers are always the same number. Ford and Fulkerson proved it in 1956, as did Elias, Feinstein and Shannon independently that year. Why should shipping and sabotage agree exactly?

Let us get one half of the answer cheaply, and then work for the other.

Draw any line through the network that puts the source on one side and the destination on the other — a cut. Now think about a single unit of flow leaving the source and arriving at the destination. It has to end up on the far side, so somewhere along its path it must cross the line. Every unit must. So the total flow cannot exceed the total capacity of the links crossing that line in the forward direction.

That holds for every cut, so the maximum flow is at most the smallest cut. This is the easy half, and notice it needed nothing but conservation and counting: whatever goes in comes out, and everything must cross.

But this only gives an upper bound. A ceiling is not an equality. Why should the flow actually reach the smallest cut, rather than getting stuck somewhere below it? Bounds like this are usually loose.

Here is where the real work is. Suppose you push flow through greedily until no unsaturated path from source to destination remains. Are you finished? Not necessarily — and this is the trap the whole subject is built around. Sending flow down one route can block a better arrangement, and a greedy solver can be stranded at a value below the true maximum.

So we need a way to say "this route is full, but the flow through it could be rerouted". That is the residual network. Alongside each link, record how much spare capacity is left going forwards, and also how much flow is currently on it — because flow already sent can be cancelled, which is a way of moving forwards. An augmenting path is any route from source to destination in this residual network, and it may use spare forward capacity, or it may undo an earlier commitment to free a better one.

Now the argument closes. Suppose no augmenting path exists at all. Let S be the set of nodes still reachable from the source through the residual network, and T everything else. The destination is in T, because there is no path to it — so this is a genuine cut. What is true of the links crossing from S to T? Each must be completely full: if any had spare capacity, its far end would have been reachable, and would have been in S. And what of the links running back from T into S? Each must carry zero flow: any flow on such a link could have been cancelled, and again its tail would have been reachable.

Read those two facts together. Every forward link across the cut is full, and every backward link is empty, so the flow crossing this particular cut is exactly its capacity — nothing is lost to backflow. But we already showed the flow can never exceed any cut's capacity. So this cut is a smallest one, and the flow is a largest one, and the two numbers coincide.

Notice what carried the argument: not an algorithm, but a stopping condition. The moment the residual network stops connecting source to destination, it hands you the certificate — the cut — that proves the flow is optimal. That is why the theorem is more than an interesting coincidence: it turns "I could not find a better route" into "no better route exists".

One caveat about practice. The argument shows termination gives optimality, but not that a naive search terminates quickly, or at all: with irrational capacities the original augmenting-path procedure can fail to converge. Choosing paths sensibly — shortest ones, as Edmonds and Karp did — fixes this and gives a polynomial bound.

The misconception worth naming is that the bottleneck must be a single narrow link. It usually is not: the minimum cut is a set of links whose capacities add up, and a network can have several distinct minimum cuts of equal value. Widening one link may buy nothing, because another cut of the same size is waiting behind it.

The second refinement is what makes the theorem useful rather than merely true: it gives a checkable certificate. You cannot verify a claimed maximum by inspecting the flow alone, but hand over a cut of equal capacity and the easy half of the argument settles it in a line. Optimality that would need exhaustive search becomes a one-step check.

That structure is why the result reappears far from pipes: since integer capacities always admit an integer maximum flow, the theorem specialises into Konig's theorem on bipartite matchings, Menger's theorem on disjoint paths, and others — the same duality in different clothes.

• Menger's theorem and Konig's theorem, both recoverable from this one.
• The Edmonds-Karp rule, and why shortest augmenting paths guarantee termination.
• Linear programming duality, of which this theorem is the best-known combinatorial instance.
• Minimum-cost flow, where links carry a price per unit as well as a capacity.

Every term the collection defines is gathered in the glossary.