Network Flows and the Max-Flow Min-Cut Theorem

⚡ Key Takeaways

One-line statement: In any network, the maximum flow from a source to a sink equals the minimum capacity of a cut separating them. Formally, $\max |f| = \min c(S,T)$ . Applies to transportation, scheduling, image segmentation, bipartite matching, and reliability. Established by L. R. Ford Jr. and D. R. Fulkerson (1956) and independently by P. Elias, A. Feinstein, and C. E. Shannon.

💡 The Core Insight

Every flow value is bounded above by every cut capacity (weak duality). If you can find one flow and one cut whose values are equal, both must be optimal. The augmenting-path method drives the flow up until no augmenting path remains; the set of vertices reachable from $s$ in the leftover ("residual") network then defines a cut whose capacity equals the achieved flow. Equality is not a coincidence — it is forced by the absence of any further augmenting path.

DefinitionFlow Network

A flow network is a tuple $(G, c, s, t)$ where:

$G = (V, E)$ is a directed graph,
$c : E \to \mathbb{R}_{\ge 0}$ assigns a capacity $c(u,v) \ge 0$ to each edge (we set $c(u,v) = 0$ if $(u,v) \notin E$ ),
$s \in V$ is the source, $t \in V$ is the sink, with $s \ne t$ .

A flow is a function $f : V \times V \to \mathbb{R}$ satisfying two constraints. The capacity constraint:

1

\quad 0 \le f(u,v) \le c(u,v) \quad \text{for all } (u,v) \in E.

Derivation hint: The flow on each edge is nonnegative and may not exceed its capacity; this is a definitional requirement, not a derived fact. And flow conservation at every internal vertex $u \in V \setminus \{s,t\}$ :

2

\quad \sum_{v \in V} f(v,u) \;=\; \sum_{v \in V} f(u,v).

Derivation hint: "Flow in = flow out" at every node except the source and sink — analogous to Kirchhoff's current law for charge conservation. The value of the flow is the net flow out of the source:

3

\quad |f| \;=\; \sum_{v \in V} f(s,v) \;-\; \sum_{v \in V} f(v,s).

Derivation hint: Total flow leaving $s$ minus any flow returning to $s$ ; by conservation this equals the net flow into $t$ .

DefinitionCut and Cut Capacity

An $s$ - $t$ cut is a partition $(S, T)$ of $V$ with $s \in S$ and $t \in T$ (so $T = V \setminus S$ ). Its capacity counts only edges crossing forward from $S$ to $T$ :

4

\quad c(S,T) \;=\; \sum_{u \in S}\sum_{v \in T} c(u,v).

Derivation hint: Backward edges (from $T$ to $S$ ) contribute nothing to capacity; only the forward-crossing edges constrain throughput. The net flow across the cut is forward minus backward flow:

5

\quad f(S,T) \;=\; \sum_{u \in S}\sum_{v \in T} f(u,v) \;-\; \sum_{u \in S}\sum_{v \in T} f(v,u).

Derivation hint: Subtract the flow returning across the cut from the flow crossing it; this signed quantity will turn out to equal $|f|$ for every cut.

DefinitionResidual Network

Given a flow $f$ , the residual capacity is

6

\quad c_f(u,v) \;=\; \big(c(u,v) - f(u,v)\big) \;+\; f(v,u).

Derivation hint: Forward slack $c(u,v)-f(u,v)$ tells how much more you can push; the term $f(v,u)$ allows you to "cancel" flow already sent backward, modeled as a virtual reverse edge. The residual network $G_f = (V, E_f)$ contains every edge $(u,v)$ with $c_f(u,v) > 0$ . An augmenting path is a directed $s \to t$ path in $G_f$ .

TheoremMax-Flow Min-Cut Theorem (Ford–Fulkerson 1956)

For any flow network $(G,c,s,t)$ , the following three statements are equivalent for a flow $f$ : 1. $f$ is a maximum flow. 2. The residual network $G_f$ contains no augmenting path. 3. $|f| = c(S,T)$ for some $s$ - $t$ cut $(S,T)$ . Consequently:

7

\quad \max_{f} |f| \;=\; \min_{(S,T)} c(S,T).

Derivation hint: Weak duality gives $\le$ ; the augmenting-path-free condition constructs a cut achieving equality, giving $\ge$ .

ProofProof of the Max-Flow Min-Cut Theorem

Step 1 — Flow across any cut equals $|f|$ . We claim $f(S,T) = |f|$ for every cut $(S,T)$ . Sum the conservation equation [2] over all $u \in S$ . The source $s$ contributes its net outflow $|f|$ (by [3]), while every internal $u \in S$ contributes $0$ . Expanding $\sum_{u\in S}\big(\sum_v f(u,v) - \sum_v f(v,u)\big)$ , all terms between two vertices both inside $S$ cancel pairwise, leaving exactly the net flow from $S$ to $T = V\setminus S$ . Hence:

8

\quad f(S,T) \;=\; |f| \quad \text{for every } s\text{-}t \text{ cut } (S,T).

Derivation hint: Telescoping cancellation of internal edges; only cut-crossing terms survive, and conservation kills all internal-vertex net flows.

Step 2 — Weak duality. Using [5] and [1], the backward term is $\ge 0$ and each forward $f(u,v) \le c(u,v)$ :

9

\quad |f| = f(S,T) \le \sum_{u\in S}\sum_{v\in T} f(u,v) \le \sum_{u\in S}\sum_{v\in T} c(u,v) = c(S,T).

Derivation hint: Drop the nonnegative backward term, then bound each forward flow by its capacity. So $|f| \le c(S,T)$ for any flow and any cut. Thus $\max|f| \le \min c(S,T)$ .

Step 3 — (1)⇒(2). If an augmenting path $P$ existed in $G_f$ , let $\delta = \min_{(u,v)\in P} c_f(u,v) > 0$ . Pushing $\delta$ along $P$ produces a valid flow of value $|f| + \delta$ , contradicting maximality. So no augmenting path can exist.

Step 4 — (2)⇒(3). Suppose $G_f$ has no $s$ - $t$ path. Define

S = \{\, v \in V : v \text{ reachable from } s \text{ in } G_f \,\}, \qquad T = V \setminus S.

Then $s \in S$ and $t \in T$ (else $t$ would be reachable). For every $u \in S, v \in T$ :

The forward edge must be saturated: $f(u,v) = c(u,v)$ , otherwise $c_f(u,v) > 0$ would make $v$ reachable.
Any backward flow must be zero: $f(v,u) = 0$ , otherwise $c_f(u,v) \ge f(v,u) > 0$ again makes $v$ reachable.

Substituting into [5]:

10

\quad |f| = f(S,T) = \sum_{u\in S}\sum_{v\in T} c(u,v) - 0 = c(S,T).

Derivation hint: Saturation of forward edges and absence of backward flow turn inequality [9] into equality.

Step 5 — (3)⇒(1). If $|f| = c(S,T)$ for some cut, then by weak duality no flow can exceed $c(S,T)$ , so $f$ is maximum and $(S,T)$ is minimum. This closes the cycle of equivalences and proves [7]. $\blacksquare$

∎

TheoremIntegrality Theorem

If every capacity $c(u,v)$ is an integer, then there exists a maximum flow $f$ in which $f(u,v)$ is an integer for every edge.

ProofIntegrality

Run Ford–Fulkerson starting from the zero flow. Each augmentation increases the flow by an integer $\delta$ (the residual capacities along the path are integers when capacities and the current flow are integers). The value strictly increases by $\ge 1$ each step and is bounded above by $c(S,T) < \infty$ , so the process terminates after finitely many steps with an integral maximum flow. $\blacksquare$

∎

LR

Lester Randolph Ford Jr. & Delbert Ray Fulkerson

1927–2017 / 1924–1976

Working at the RAND Corporation in the mid-1950s, Ford and Fulkerson were motivated by a Cold War problem posed by the U.S. Air Force: how much traffic could the Soviet rail network carry, and where was it most vulnerable to interdiction? The dual question — find the cheapest set of rail links to cut — is the minimum cut. Their 1956 paper "Maximal Flow Through a Network" turned this military logistics puzzle into a foundational theorem of combinatorial optimization. Fulkerson later co-authored the definitive monograph Flows in Networks (1962). The same result was discovered independently and nearly simultaneously by Peter Elias, Amiel Feinstein, and Claude Shannon in an information-theoretic context.

🧠 Intuition

Think of the network as a system of water pipes. Capacities are pipe diameters; flow is gallons per second. You can never push more water from source to sink than the tightest "wall" of pipes you'd have to sever to fully disconnect them — that wall is the minimum cut. The augmenting-path algorithm is like repeatedly finding any open route from source to sink and cranking up the flow along it. The genius of the residual network is the backward edges: if you over-committed flow on some pipe, a backward residual edge lets a later augmenting path "undo" part of that decision and reroute. This rerouting capability is exactly what guarantees the greedy process reaches the true global optimum rather than getting stuck. When no route remains — even counting these undo-options — the set of pipes you can still reach forms one side of the bottleneck cut.

Figure

A flow network with a minimum cut. Forward edges from

S

(left) to

T

(right) are saturated; their capacities sum to the max-flow value.

ExampleA Small Network by Hand

Given: Vertices $\{s, a, b, t\}$ with capacities $c(s,a)=10$ , $c(s,b)=10$ , $c(a,b)=2$ , $c(a,t)=4$ , $c(b,t)=10$ .

Step 1 — Augment along $s \to a \to t$ . Bottleneck $= \min(10,4) = 4$ . Push 4. Flow value $= 4$ .

Step 2 — Augment along $s \to b \to t$ . Bottleneck $= \min(10,10) = 10$ . Push 10. Flow value $= 14$ .

Step 3 — Augment along $s \to a \to b \to t$ . Residual capacities: $c_f(s,a)=10-4=6$ , $c_f(a,b)=2$ , $c_f(b,t)=10-10=0$ . The edge $b\to t$ is saturated, so this path is blocked. No other $s$ - $t$ path exists in $G_f$ (from $a$ , the only outlet $a\to b$ leads to $b$ , whose only outlet $b\to t$ is full).

Step 4 — Identify the cut. Reachable from $s$ in $G_f$ : $S = \{s, a, b\}$ (we reach $b$ via $a\to b$ ), so $T = \{t\}$ . Cut capacity $= c(a,t) + c(b,t) = 4 + 10 = 14$ .

Answer:

\boxed{\;\max|f| = 14 \text{ units},\quad \text{min cut} = (\{s,a,b\},\{t\}) \text{ with capacity } 14\;}

Flow equals cut capacity, confirming optimality.

ExampleBipartite Matching via Max-Flow

Given: Three applicants $\{x_1, x_2, x_3\}$ and three jobs $\{y_1, y_2, y_3\}$ . Compatible pairs: $x_1$ – $\{y_1,y_2\}$ , $x_2$ – $\{y_1\}$ , $x_3$ – $\{y_2,y_3\}$ . We want the largest possible matching.

Construction: Add source $s \to x_i$ (capacity 1 each), edges $x_i \to y_j$ (capacity 1) for each compatible pair, and $y_j \to t$ (capacity 1 each).

Step 1 — Augment $s\to x_1\to y_1\to t$ . Value $1$ . Step 2 — Augment $s\to x_3\to y_2\to t$ . Value $2$ . Step 3 — Augment $s\to x_2\to y_1\to t$ ? Edge $y_1\to t$ saturated. Try $s\to x_2\to y_1$ , then use backward residual $y_1 \to x_1$ (since $f(x_1,y_1)=1$ ), then $x_1 \to y_2$ ? But $y_2 \to t$ is saturated. Dead end. No augmenting path remains.

Step 4 — Verify with min cut. Set $S=\{s,x_2,x_1,y_1\}$ reachable from $s$ . Crossing edges: $x_1\to y_2$ (cap 1), $s\to x_3$ (cap 1)... computing gives min cut capacity $= 2$ .

Answer:

\boxed{\;\text{Maximum matching size} = 2:\ \{(x_1,y_1),(x_3,y_2)\}\;}

By the integrality theorem the flow is $0$ / $1$ , so it corresponds to an actual matching — this is König's theorem in disguise.

⚠️ Common mistake

The minimum cut is not unique, but its value is. A network can have several distinct minimum cuts, all with the same capacity. Likewise the maximum flow itself need not be unique — many different flow assignments can achieve the optimal value. Only the value $\max|f| = \min c(S,T)$ is invariant.

Cut capacity counts only forward edges. A frequent error is to add edges going from $T$ back to $S$ into the cut capacity. By definition [4], backward edges contribute zero to capacity — though their flow is subtracted in the net-flow formula [5].

Ford–Fulkerson with arbitrary path choice may not terminate for irrational capacities. Termination and polynomial running time require care: the Edmonds–Karp refinement (always augment along a shortest augmenting path via BFS) runs in $O(VE^2)$ time and always terminates.

CounterexampleNon-Termination with Irrational Capacities

Ford and Fulkerson exhibited a network with one irrational capacity equal to $\phi = (\sqrt 5 - 1)/2$ (the golden ratio) on which a poorly chosen sequence of augmenting paths makes the flow value converge to a number strictly less than the true maximum — the algorithm runs forever without reaching optimality. The augmentation amounts form a geometric series in powers of $\phi$ that sums to a finite value below $\max|f|$ . This shows the bare augmenting-path scheme is not an algorithm unless the path-selection rule is constrained (e.g., shortest path, or capacity scaling). With integer or rational capacities, termination is guaranteed.

connection

The Max-Flow Min-Cut Theorem is a special case of Linear Programming Duality: max-flow is a linear program, and its dual is exactly the min-cut LP relaxation; strong duality plus integrality of the constraint matrix (total unimodularity) yields the integer min cut. It generalizes König's Theorem (max matching = min vertex cover in bipartite graphs) and Hall's Marriage Theorem (a perfect matching exists iff every set of vertices has enough neighbors). It is the engine behind <a class="wiki-link" href="/wiki/math-discrete-mengers-theorem">Menger's Theorem</a> — the maximum number of edge-disjoint $s$ - $t$ paths equals the minimum number of edges whose removal disconnects $s$ from $t$ . It also relates to Linear Programming Duality and to Network Reliability. The minimum-cost variant connects to Transportation Problem and the Hungarian Algorithm.

🔬 Where this appears

⏳ History

- 1927 — Karl Menger proves <a class="wiki-link" href="/wiki/math-discrete-mengers-theorem">Menger's Theorem</a> on disjoint paths and vertex connectivity, a graph-theoretic ancestor of max-flow min-cut.

- 1931 — Dénes König and Jenő Egerváry establish the min-vertex-cover / max-matching duality in bipartite graphs.

- 1951 — George Dantzig formulates the simplex method and studies the transportation problem, providing the linear-programming backdrop.

- 1954 — Ford and Fulkerson begin work at RAND on the Soviet rail interdiction problem.

- 1955 — Independently, T. E. Harris and F. S. Ross (also at RAND) frame the rail-capacity problem; their secret report poses the dual interdiction question.

- 1956 — Ford & Fulkerson publish "Maximal Flow Through a Network," proving the theorem; Elias, Feinstein, and Shannon prove an equivalent result independently the same year.

- 1962 — Ford & Fulkerson's monograph Flows in Networks appears, codifying the field.

- 1969 — A counterexample to Ford–Fulkerson termination on irrational capacities is constructed.

- 1972 — Jack Edmonds and Richard Karp give the first polynomial-time max-flow algorithm (

O(VE^2)

) using shortest augmenting paths; Dinic independently develops a faster blocking-flow algorithm (1970).

open-problem

How fast can max-flow be computed? For decades the best general bounds hovered around $O(VE)$ (Orlin 2013) and $O(V^3)$ . A breakthrough in 2022 by Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva gave an almost-linear-time algorithm running in $m^{1+o(1)}$ for min-cost flow (and hence max-flow), settling a long-standing question for sparse graphs — though the algorithm is highly intricate and not yet practical. Open questions remain about deterministic almost-linear algorithms, the precise complexity of dynamic (incremental/decremental) max-flow, and tight bounds for parametric and multi-commodity flows. Notably, multi-commodity max-flow min-cut does not satisfy exact duality: with several source-sink pairs, the max total flow can be strictly less than the min cut, with a known $O(\log k)$ flow-cut gap — a vibrant area connecting to metric embeddings and approximation algorithms.

Network Flows and the Max-Flow Min-Cut Theorem

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also