Network Flows and the Max-Flow Min-Cut Theorem

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.

A flow network is a directed graph in which each edge carries a nonnegative capacity, and we wish to push as much "stuff" as possible from a designated source $s$ to a designated sink $t$ without exceeding any edge's capacity and while conserving flow at every intermediate node. The Max-Flow Min-Cut Theorem states that this maximum throughput is exactly limited by the cheapest "bottleneck" — the minimum-capacity set of edges whose removal disconnects $s$ from $t$ . This duality is one of the most elegant results in combinatorial optimization, and it is constructive: algorithms like Ford–Fulkerson simultaneously compute the optimal flow and exhibit the cut certifying its optimality. The surprising fact is that an utterly local, greedy-looking process of finding augmenting paths terminates at a globally optimal solution, and even more surprising, integer capacities guarantee an integer optimal flow — a fact with deep consequences for matching and combinatorics.

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.

Formal Statement

Flow Network

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

$G = (V, E)$ is a directed graph,
$c : E \to R_{\geq 0}$ assigns a capacity $c (u, v) \geq 0$ to each edge (we set $c (u, v) = 0$ if $(u, v) \in / E$ ),
$s \in V$ is the source, $t \in V$ is the sink, with $s \neq = t$ .

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

0 \leq f (u, v) \leq c (u, v) for all (u, v) \in E .

⟳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 ∖ {s, t}$ :

v \in V \sum f (v, u) = v \in V \sum f (u, v) .

⟳"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:

∣ f ∣ = v \in V \sum f (s, v) - v \in V \sum f (v, s) .

⟳Total flow leaving

s

minus any flow returning to

s

; by conservation this equals the net flow into

t

Cut 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 ∖ S$ ). Its capacity counts only edges crossing forward from $S$ to $T$ :

c (S, T) = u \in S \sum v \in T \sum c (u, v) .

⟳Backward edges (from

T

S

) contribute nothing to capacity; only the forward-crossing edges constrain throughput.

The net flow across the cut is forward minus backward flow:

f (S, T) = u \in S \sum v \in T \sum f (u, v) - u \in S \sum v \in T \sum f (v, u) .

⟳Subtract the flow returning across the cut from the flow crossing it; this signed quantity will turn out to equal

∣ f ∣

for every cut.

Residual Network

Given a flow $f$ , the residual capacity is

c_{f} (u, v) = (c (u, v) - f (u, v)) + f (v, u) .

⟳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}$ .

Max-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$ :

$f$ is a maximum flow.
The residual network $G_{f}$ contains no augmenting path.
$∣ f ∣ = c (S, T)$ for some $s$ - $t$ cut $(S, T)$ .

Consequently:

f max ∣ f ∣ = (S, T) min c (S, T) .

⟳Weak duality gives

\leq

; the augmenting-path-free condition constructs a cut achieving equality, giving

\geq

Why It Holds

Proof 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} (\sum_{v} f (u, v) - \sum_{v} f (v, u))

, all terms between two vertices both inside

S

cancel pairwise, leaving exactly the net flow from

S

T = V ∖ S

. Hence:

f (S, T) = ∣ f ∣ for every s - t cut (S, T) .

⟳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

\geq 0

and each forward

f (u, v) \leq c (u, v)

∣ f ∣ = f (S, T) \leq u \in S \sum v \in T \sum f (u, v) \leq u \in S \sum v \in T \sum c (u, v) = c (S, T) .

⟳Drop the nonnegative backward term, then bound each forward flow by its capacity.

So $∣ f ∣ \leq c (S, T)$ for any flow and any cut. Thus $max ∣ f ∣ \leq min c (S, T)$ .

Step 3 — (1)⇒(2). If an augmenting path

P

existed in

G_{f}

, let

δ = min_{(u, v) \in P} c_{f} (u, v) > 0

. Pushing

δ

along

P

produces a valid flow of value

∣ f ∣ + δ

, 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 reachable from s in G_{f}}, T = V ∖ 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) \geq f (v, u) > 0$ again makes $v$ reachable.

Substituting into [5]:

∣ f ∣ = f (S, T) = u \in S \sum v \in T \sum c (u, v) - 0 = c (S, T) .

⟳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].

■

Integrality 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.

Integrality

Run Ford–Fulkerson starting from the zero flow. Each augmentation increases the flow by an integer $δ$ (the residual capacities along the path are integers when capacities and the current flow are integers). The value strictly increases by $\geq 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. $■$

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.

Building 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.

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.

Worked Examples

A 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

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:

max ∣ f ∣ = 14 units, min cut = ({s, a, b}, {t}) with capacity 14

Flow equals cut capacity, confirming optimality.

Bipartite 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:

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 Misconceptions

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 (V E^{2})

time and always terminates.

Non-Termination with Irrational Capacities

Ford and Fulkerson exhibited a network with one irrational capacity equal to $ϕ = (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 $ϕ$ 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.

Connections

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 Menger's Theorem — 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.

Real-World Applications

Transportation and logistics — Routing maximum freight through rail, road, or pipeline networks, and identifying bottleneck links (the original RAND motivation).
Image segmentation (computer vision) — The graph-cuts method models pixels as nodes and finds a min cut to separate foreground from background, used in interactive photo editing and medical imaging.
Bipartite assignment — Matching workers to tasks, students to schools, or organ donors to recipients (kidney exchange programs) via max-flow with unit capacities.
Airline crew and project scheduling — Modeling resource constraints as capacities to maximize feasible assignments.
Network reliability and security — The minimum cut identifies the most vulnerable set of communication links; relates to denial-of-service vulnerability analysis.
Baseball elimination — Determining whether a sports team can still mathematically win its division reduces to a max-flow feasibility test.
Open-pit mining and project selection — Choosing a maximally profitable subset of projects with precedence constraints maps to a min-cut problem (the "maximum closure" problem).

Historical Development

1927 — Karl Menger proves Menger's Theorem 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 (V E^{2})$ ) using shortest augmenting paths; Dinic independently develops a faster blocking-flow algorithm (1970).

Subtleties & Limits

How fast can max-flow be computed? For decades the best general bounds hovered around

O (V E)

(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 (lo g k)

flow-cut gap — a vibrant area connecting to metric embeddings and approximation algorithms.