Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp: Visual walkthrough

Step 0 — The three things we are allowed to talk about

Before any theorem, we need three objects on the page. Let us draw them.

PICTURE. Look at the figure. Black dots are junctions, black arrows are pipes, and the number on each arrow is its capacity. The red dots are the two special ones: $s$ on the left, $t$ on the right.

Figure — Network flow — max-flow min-cut theorem, Ford-Fulkerson, Edmonds-Karp

We will use this exact network the whole way down, so remember it: $s \to a$ holds 3, $s \to b$ holds 2, $a \to b$ holds 1, $a \to t$ holds 2, $b \to t$ holds 3.

Step 1 — What "a flow" actually is (and its two laws)

We now put water into the pipes. A flow $f (u, v)$ is a second number on each arrow: how much water is actually running through that pipe right now (not just how much it could hold).

PICTURE. Each pipe now shows a fraction $f / c$ — running water over capacity. Watch dot $a$ (circled red): the water arriving equals the water leaving. That balance is Law 2 made visible.

Step 2 — Drawing a "cut": a wall between $s$ and $t$

Now forget flow for a moment. Imagine slicing the whole network into two teams of dots.

PICTURE. The red dashed line is the wall. Everything left of it is $S$ (blue-shaded region, tap side); everything right is $T$ (bucket side). The two arrows that cross forward are highlighted — their capacities added together are the cut's cost. The one backward arrow crossing the wall is drawn faint: it is free.

Step 3 — The bookkeeping trick: flow across a cut is the flow value

Here is the first real derivation. We claim: no matter where you draw the wall, the net water crossing it forward equals $∣ f ∣$ .

Let us make it exact. Add up Law 2 over every dot in $S$ (and the value-definition for $s$ ):

$∣ f ∣ = \sum_{x \in S} (out of x v \sum f (x, v) - into x v \sum f (v, x))$

Now split each arrow by where its two ends live:

Both ends in $S$ (internal): the arrow's flow appears once as " $+ f$ out of one $S$ -dot" and once as " $- f$ into another $S$ -dot". They cancel.
One end in $S$ , one in $T$ (crossing): survives.

What is left is exactly the crossing flow:

$∣ f ∣ = forward across wall u \in S, v \in T \sum f (u, v) - backward across wall u \in S, v \in T \sum f (v, u)$

PICTURE. Internal arrows are drawn grey and paired with a $+ / -$ tag to show they cancel. Only the red crossing arrows survive the sum. That surviving red total is $∣ f ∣$ .

Step 4 — Weak duality: every flow is trapped below every cut

Take the boxed equation from Step 3 and squeeze each piece.

$∣ f ∣ = forward \sum f (u, v) - backward \sum f (v, u)$

Forward flows obey Law 1: $f (u, v) \leq c (u, v)$ . So the first sum is at most $\sum c (u, v) = c (S, T)$ .
Backward flows obey Law 1: $f (v, u) \geq 0$ . So the second sum is at least $0$ , and we are subtracting it — subtracting something non-negative only makes $∣ f ∣$ smaller.

Chain both facts:

$∣ f ∣ \leq \sum c (forward) - 0 = c (S, T)$

PICTURE. A number line. The blue tick $∣ f ∣$ sits somewhere; the red tick $c (S, T)$ sits to its right. The arrow shows $∣ f ∣$ can never jump past any cut. Do this for the smallest cut and you get $max ∣ f ∣ \leq min c (S, T)$ : the best flow is fenced in below the cheapest wall.

Step 5 — The residual graph: leftovers plus "undo" arrows

To reach the ceiling we need a machine that improves a flow. That machine is the residual graph — a redrawing of the network showing where water can still move.

PICTURE. One original pipe (top, $f = 2$ of $c = 3$ ) becomes two residual arrows below: a solid forward arrow labelled $c - f = 1$ (room left) and a red dashed backward arrow labelled $f = 2$ (the refund). One red dashed arrow is the star of this figure — it is the only new idea here.

An augmenting path is any route from $s$ to $t$ using residual arrows with positive capacity. Its bottleneck is the smallest capacity along it. Pushing that much strictly raises $∣ f ∣$ — so as long as an augmenting path exists, we are not at the maximum.

Step 6 — The knockout: no augmenting path builds the min cut for free

Now the punchline. Suppose we have run the machine until no augmenting path from $s$ to $t$ exists in the residual graph. We will show this flow equals a cut — proving it maximal.

Build the cut automatically. Let

$S = {dots reachable from s using residual arrows}, T = V ∖ S .$

Since no augmenting path reaches $t$ , we know $t \in T$ . So $(S, T)$ is a legal cut. Now look at any arrow crossing the wall:

Forward pipe $u \to v$ ( $u \in S, v \in T$ ): if it had leftover ( $f < c$ ) there'd be a residual forward arrow into $v$ , making $v$ reachable — contradiction. So it is saturated: $f (u, v) = c (u, v)$ .
Backward pipe $v \to u$ ( $v \in T, u \in S$ ): if it carried flow ( $f > 0$ ) it would create a residual arrow $u \to v$ into $v$ , again making $v$ reachable — contradiction. So $f = 0$ on it.

Plug into Step 3's boxed identity:

$∣ f ∣ = all saturated \sum c (forward) - no backward flow 0 = c (S, T)$

PICTURE. The residual graph after the machine halts. Reachable dots ( $S$ ) are shaded; the red wall separates them from $T$ . Every forward arrow across the wall is drawn thick-red and stamped "FULL"; every backward arrow is stamped "EMPTY". The flow leaking across exactly fills the wall.

Combine with Step 4: we found a flow equal to a cut. Step 4 said flow $\leq$ cut for all pairs, so neither can improve — this flow is maximum and this cut is minimum. $■$

Step 7 — Edge and degenerate cases (nothing left unshown)

A theorem you cannot trust at the corners is not a theorem. Check them.

Worked example The corners, each resolved

Zero flow $∣ f ∣ = 0$ . Perfectly legal ( $f \equiv 0$ obeys both laws). Weak duality still holds: $0 \leq c (S, T)$ . If additionally $s$ has no outgoing pipes, $0$ is the max — cut $S = {s}$ has capacity $0$ .

$s$ and $t$ disconnected. No path exists, so every flow is $0$ , and the min cut is $0$ (the wall right after $s$ crosses no pipe). $0 = 0$ : theorem holds.

A pipe of capacity $0$ . It never carries flow ( $0 \leq f \leq 0$ ), never appears in the residual graph. Harmless — it is as if the pipe were absent.

Backward arrow across the cut carrying flow. Impossible at the optimum (Step 6 forbids it), but during the run it can happen — that is exactly the refund coupon doing useful rerouting.

Irrational capacities. Weak duality (Step 4) still holds — it never used integers. But the algorithm choosing paths badly may push shrinking amounts forever and never terminate. This is why BFS-based path choice (Dinic's Algorithm, Edmonds–Karp) matters: it bounds the step count independent of capacities.

PICTURE. Four tiny networks side by side, each illustrating one corner case, with its max-flow value stamped in red. Seeing them together confirms the equality survives every degenerate input.

The one-picture summary

Here is the entire derivation compressed into a single diagram: a flow value pinned between "any cut" above and pushed up by "augmenting paths" below, meeting exactly when the residual graph runs dry.

Ceiling (Step 4): every cut is an upper wall — $∣ f ∣ \leq c (S, T)$ .
Elevator (Steps 5–6): each augmenting path lifts $∣ f ∣$ by its bottleneck.
Landing (Step 6): when no path remains, the reachable set $S$ is a cut of the same value. Ceiling met. Done.

Recall Feynman retelling — the whole walkthrough in plain words

You have pipes from a tap $s$ to a bucket $t$ . Water can only be as much as pipes hold, and no junction stores water — in equals out. Draw any wall splitting tap-side from bucket-side; count only the pipes pointing forward through it. Because junctions don't hoard, all the water the tap emits has to cross that wall — so water-crossing-the-wall equals the total water sent. Forward pipes across the wall can't carry more than they hold, and backward pipes only subtract, so the water sent can never beat the wall's cost — no matter which wall. That's the ceiling. To reach it, keep finding any still-open route from tap to bucket and push water through — and crucially, keep refund coupons (backward arrows) so you can pull water back out of a bad route and reroute it. When absolutely no open route remains, look at every dot you can still reach from the tap: that reachable set is a wall, every forward pipe across it is completely full, every backward one is empty — so the water sent exactly equals this wall's cost. Ceiling touched. Max flow = min cut.

Recall

Why does summing conservation over all of $S$ leave only cut-crossing flow? ::: Internal arrows appear once as $+ f$ and once as $- f$ and cancel; only arrows with one endpoint in $T$ survive. Which arrows across a cut count toward its capacity? ::: Only forward $S \to T$ arrows; backward ones are free. What does "no augmenting path" let you build for free? ::: The set $S$ of residual-reachable dots, a cut whose capacity equals the current flow — proving both optimal. Why can the algorithm fail to terminate with irrational capacities? ::: A bad path choice can push ever-shrinking bottleneck amounts forever; BFS path choice fixes this.