What the max-flow min-cut theorem is really saying — Duality in action

The maximum flow through a network equals the minimum capacity of a cut separating source from sink. This elegant duality is one of the most beautiful results in combinatorics. We develop intuition through water pipes, augmenting paths, and LP duality.

Folio Official

March 1, 2026

At the heart of network flow theory lies the max-flow min-cut theorem, one of the most beautiful results in all of graph theory. It asserts that the maximum amount of flow that can be pushed from source to sink equals the minimum cost of severing the network – a statement equating two quantities that, on the face of it, have nothing to do with each other. This is duality in its purest form.

1 What is a flow? – The water-pipe analogy

Definition 1 (Network).

A network consists of a directed graph

G = (V, A)

, a capacity function

c : A \to R_{\geq 0}

, and two distinguished vertices: a source

s

and a sink

t

Think of a network of water pipes. The source $s$ is a water treatment plant, the sink $t$ is a neighborhood of houses, the arcs are pipes, and the capacity of each arc is the maximum volume of water per unit time that the pipe can carry.

Definition 2 (Flow).

A flow on a network

(G, c, s, t)

is a function

f : A \to R_{\geq 0}

satisfying:

Capacity constraint: $0 \leq f (u, v) \leq c (u, v)$ for every arc $(u, v) \in A$ .
Flow conservation: For every vertex $v \neq = s, t$ ,
$u : (u, v) \in A \sum f (u, v) = w : (v, w) \in A \sum f (v, w) .$

The value of the flow, denoted

∣ f ∣

, is the total flow leaving

s

∣ f ∣ = \sum_{w : (s, w) \in A} f (s, w)

Remark 3.

Flow conservation says that intermediate nodes neither create nor absorb water: whatever flows in must flow out. This is the fluid analogue of Kirchhoff's current law.

2 What is a cut? – The network's weakest link

Definition 4 (

s

t

cut).

A partition

(S, T)

of the vertex set with

s \in S

and

t \in T

is called an

s

t

cut. The capacity of the cut is

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

A cut is a line that separates the network into an $s$ -side and a $t$ -side. To sever the connection between $s$ and $t$ , every arc from $S$ to $T$ must be "cut," and the total capacity of those arcs is the cost of the severance.

Remark 5 (The highway bottleneck).

Imagine transporting goods from Tokyo to Osaka. If you could block a single stretch of road to halt all shipments, that would be a cut. The minimum-cost set of road closures that completely blocks the route is the minimum cut.

3 Weak duality – understanding the inequality first

Theorem 6 (Weak duality).

For any flow

f

and any

s

t

cut

(S, T)

∣ f ∣ \leq c (S, T) .

This is intuitively obvious. Every unit of flow traveling from $s$ to $t$ must cross the cut $(S, T)$ at some point, and the amount crossing cannot exceed the capacity of the arcs it traverses.

Remark 7.

In the water-pipe analogy: no matter how cleverly you route the water, you cannot push more through the system than the capacity of its narrowest cross-section.

4 The max-flow min-cut theorem – equality holds

Weak duality gives us " $\leq$ ." The remarkable fact is that equality is always achieved.

Theorem 8 (Max-flow min-cut theorem (Ford–Fulkerson)).

In a network

(G, c, s, t)

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

That is, the value of a maximum flow equals the capacity of a minimum cut.

Remark 9 (Why equality holds – the augmenting-path intuition).

Suppose a flow

f

is not yet maximum. Then there must exist a path from

s

t

along which additional flow can be pushed – an augmenting path in the residual graph. As long as augmenting paths exist, we keep pushing more flow.

When no augmenting path remains, consider the set

S

of vertices reachable from

s

in the residual graph, and let

T = V ∖ S

. Every arc from

S

T

in the original network must be saturated (otherwise an augmenting path would exist). Therefore

∣ f ∣ = c (S, T),

which simultaneously proves that

f

is a maximum flow and

(S, T)

is a minimum cut.

5 LP duality – a deeper perspective

The max-flow min-cut theorem is, in fact, a special case of LP duality (the strong duality theorem of linear programming).

Remark 10.

The maximum flow problem can be formulated as a linear program:

max ∣ f ∣ subject to 0 \leq f (e) \leq c (e), flow conservation .

Writing down the dual of this LP yields precisely the minimum cut problem. LP strong duality then guarantees

max = min

This is no coincidence. Across mathematics, "the optimal value of a maximization problem equals the optimal value of the corresponding minimization problem" is a recurring theme. The max-flow min-cut theorem is among the most elegant concrete instances of this principle.

6 Real-world applications

Example 11 (Internet bandwidth).

Let

s

be a server,

t

a client, arcs be network links, and capacities be bandwidths. The maximum flow represents the maximum data transfer rate from server to client, and the minimum cut identifies the bottleneck – the set of links whose combined bandwidth limits the entire connection.

Example 12 (Bipartite matching).

The maximum matching problem in a bipartite graph reduces to a maximum flow problem. Add a source with capacity-1 arcs to every left vertex and a sink with capacity-1 arcs from every right vertex; assign capacity 1 to the original edges. Then max flow = maximum matching size.

Example 13 (Project selection).

When a collection of interdependent projects must be selected to maximize total profit, the optimal selection can be found by solving a minimum cut problem on an appropriately constructed network.

7 Summary

Maximum flow: the greatest amount of flow that can be sent from $s$ to $t$ .
Minimum cut: the cheapest way to disconnect $s$ from $t$ .
These two quantities are always equal– when augmenting paths are exhausted, the bottleneck (the minimum cut) has been reached.
The theorem is a beautiful special case of LP duality, embodying the broader mathematical principle that "max = min."

In the next article, we enter the world of bipartite graphs and ask why everything seems to work so well there.

Graph Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

What the max-flow min-cut theorem is really saying — Duality in action

1 What is a flow? – The water-pipe analogy

2 What is a cut? – The network's weakest link

3 Weak duality – understanding the inequality first

4 The max-flow min-cut theorem – equality holds

5 LP duality – a deeper perspective

6 Real-world applications

7 Summary

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry