Two numbers that have no business being equal
In the first guide of this rung you learned to read a flow network: edges with capacities, a source s, a sink t, and a flow that obeys conservation at every middle vertex. The value of a flow is the net amount leaving s, the throughput from s to t. In the second guide you learned to increase that value: build the residual graph, find an augmenting path from s to t, and push more flow along it. Both of those were about one side of the story — pushing as much as you can. This guide introduces the other side, and then performs the small miracle of showing they meet.
The other side is a cut. Picture the vertices split into two teams: a set S that contains the source s, and the set T of everyone else, which contains the sink t. An s-t cut is exactly this partition (S, T). Its capacity is the sum of the capacities of all edges that cross from S to T — the forward edges only; edges pointing back from T to S do not count. Intuitively, a cut is a wall: to actually disconnect s from t you would have to sever every forward edge crossing the wall, and the capacity is the total cost of doing so.
Now here is the claim that ought to feel suspicious. The maximum value of any flow equals the minimum capacity of any cut. One number is the best you can do by pushing; the other is the cheapest way to block. They are defined by opposite verbs over different objects, yet they are the same number. That equality is the max-flow min-cut theorem, and earning the right to believe it is the whole job of this guide.
The easy half: any flow is trapped under any cut
Half of the theorem is almost free, and it is worth savoring because it is your first weak duality argument. Claim: for any flow f and any cut (S, T), the value of f is at most the capacity of (S, T). Not the maximum flow and the minimum cut — any of each. The reason is a bookkeeping identity. Whatever flow leaves s has to eventually cross the wall to reach t, because t lives on the far side. So the value of f equals the flow on edges going from S to T minus the flow on edges coming back from T to S.
That identity follows from conservation: sum the conservation equation over every vertex in S, and all the purely-internal flow cancels, leaving exactly the net flow crossing the boundary. Now bound it. The forward part is at most the sum of the capacities of the S-to-T edges, since flow never exceeds capacity. The backward part is a quantity we are subtracting, and flow is never negative, so subtracting it only makes the value smaller. Put together: value of f = (forward flow) - (backward flow) <= (forward flow) <= (sum of forward capacities) = capacity of the cut.
The hard half: where the residual graph pays off
Weak duality says max-flow <= min-cut. To finish the theorem we need the reverse: some flow actually reaches some cut's capacity, so they are equal, not merely ordered. The proof is the punchline of everything you built in the previous guide. The key statement is a three-way equivalence about a flow f. Either all three of these are true, or none are: (1) f is a maximum flow; (2) the residual graph of f has no augmenting path — no s-to-t path of positive residual capacity; (3) there is a cut whose capacity equals the value of f.
- (1) implies (2): if f had an augmenting path, you could push more flow along it and raise the value, so f would not be maximum. Contrapositive of exactly the augmentation step from the previous guide.
- (2) implies (3): this is the clever construction. Suppose there is no augmenting path. Let S be the set of all vertices still reachable from s in the residual graph; t is not in S, since no residual path reaches it.
- Examine the cut (S, T). Every forward edge from S to T must be saturated — carrying flow equal to its capacity — otherwise it would leave positive residual capacity and let you walk one step further into T, contradicting that S is exactly the reachable set.
- Likewise every backward edge from T to S must carry zero flow, else there would be residual capacity backward into S — again it would extend the reachable set. So forward edges are full and backward edges are empty.
- Plug that into the value identity: value of f = (forward flow) - (backward flow) = (full forward capacities) - 0 = capacity of (S, T). The weak-duality inequality has become an equality. So (3) holds, and with weak duality, f is maximum, giving (3) implies (1).
Look at what the equivalence delivers. The same condition — no augmenting path remains — that tells the Ford-Fulkerson method when to stop is the very condition that hands you a matching cut. The reachable set S in the final residual graph is not a separate computation; you can read the minimum cut straight off the last BFS or DFS the algorithm ran. The proof and the algorithm are the same object seen from two angles.
A first taste of duality
This pairing of a maximize problem with a minimize problem, where the two optimum values coincide, is the heart of duality, the deepest theme in optimization. Max-flow is a linear program: variables are the flow on each edge, the constraints are capacity (flow <= capacity) and conservation, and you maximize the value. Every linear program has a partner, its dual, obtained mechanically from the same data; minimizing the dual of the max-flow LP turns out to be — almost exactly — the min-cut problem. The general theory guarantees the two optima are equal whenever the problem is well-behaved, and max-flow min-cut is the most beloved concrete instance of that promise.
Why does this picture matter beyond elegance? Because the dual gives you a certificate. A flow alone is just a number you computed; pair it with a cut of equal capacity and you have an unforgeable proof that no larger flow exists, checkable in one pass without trusting the algorithm. That is the practical gift of weak duality: feasible solutions on the two sides bracket the true optimum, and equality nails it exactly. You will meet this primal-dual idea again well outside flow — it underlies how good lower bounds are built across optimization.
Honest limits: what the theorem does and does not promise
Be precise about what equality means. The theorem says the maximum flow value equals the minimum cut capacity — two numbers are equal. It does not say the maximizing flow or the minimizing cut is unique. A network can have many different maximum flows, and many different minimum cuts, all sharing that one common value. So "find the min cut" can have several right answers; the cut you read off the final residual graph is a minimum cut, not necessarily the one.
The clean equality also leans on assumptions worth naming. The classic statement assumes finite capacities and a single source and sink; multiple sources or sinks are handled by adding a super-source and super-sink, but you must do that conversion before the theorem applies. Integer capacities buy you an extra prize — the integrality theorem says a maximum flow exists in whole numbers — which is exactly what makes flow a clean tool for matching, where half an edge would be meaningless. With irrational capacities, plain Ford-Fulkerson can even fail to terminate, a reminder that the theorem is about existence of the equality, not about any particular algorithm reaching it.
Finally, separate the theorem from its running time. Max-flow min-cut is a statement about what is true, proven with no reference to how long anything takes. The cost of computing the common value depends entirely on how you hunt for augmenting paths: blind Ford-Fulkerson can be slow or even non-terminating, while Edmonds-Karp (shortest augmenting paths via BFS) runs in O(V E^2), and Dinic's algorithm does better with blocking flows. The duality is exact and timeless; the efficiency is a separate engineering story told by the algorithm you pick.