Folioby Interconnected
Log InSign Up

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.

FO
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→R≥0​, and two distinguished vertices: a sources and a sinkt.

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.

10
8
5
7
6
4
10
s
A
B
C
t

Definition 2 (Flow).
A flow on a network (G,c,s,t) is a function f:A→R≥0​ satisfying:

  1. Capacity constraint:0≤f(u,v)≤c(u,v) for every arc (u,v)∈A.

  2. Flow conservation: For every vertex v=s,t,

    u:(u,v)∈A∑​f(u,v)=w:(v,w)∈A∑​f(v,w).

The value of the flow, denoted ∣f∣, is the total flow leaving s: ∣f∣=∑w:(s,w)∈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-tcut).
A partition (S,T) of the vertex set with s∈S and t∈T is called an s-tcut. The capacity of the cut is
c(S,T)=u∈S,v∈T(u,v)∈A​∑​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∣≤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 "≤." 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),
fmax​∣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 to 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 to 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 to0≤f(e)≤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 TheoryMathematicsBetween the LinesNetwork FlowMax-Flow Min-CutFord-Fulkerson
FO
Folio Official

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

1 followers·107 articles
Graph Theory — Between the LinesPart 6 of 8
Previous
The Euler--Hamilton divide: why "all edges" and "all vertices" are worlds apart
Next
The magic of bipartite graphs — Why everything works

Share your expertise with the world

Write articles with LaTeX support, build your audience, and earn from your knowledge.

Start Writing — It's Free

More from Folio Official

Folio Official·March 1, 2026

Why does the greedy algorithm work for trees? — What matroids reveal

Kruskal's algorithm for minimum spanning trees is absurdly simple: sort the edges by weight and add the cheapest one that does not create a cycle. Why does this greedy strategy produce an optimal solution? The answer lies in the cut property and, more deeply, in matroids.

Graph TheoryMathematicsBetween the Lines
Folio Official·March 1, 2026

Why are trees special? — The beauty of minimal connectivity

Seven equivalent characterizations of trees all say the same thing from different angles: a tree is a connected graph with zero redundancy. Add one edge and a cycle appears; remove one edge and the graph disconnects. This article unpacks the beauty behind that knife-edge structure.

Graph TheoryMathematicsBetween the Lines
Folio Official·March 1, 2026

The magic of bipartite graphs — Why everything works

The absence of odd cycles is a single structural property, yet it makes matching, coloring, and covering all tractable at once. This article explores the remarkable power of bipartiteness through König's theorem, Hall's marriage theorem, and the reduction patterns they enable.

Graph TheoryMathematicsBetween the Lines
Folio Official·March 1, 2026

Network Flows

Flow networks, the max-flow min-cut theorem, the Ford--Fulkerson method, the Edmonds--Karp algorithm, Dinic's algorithm, and the reduction of bipartite matching to maximum flow.

Graph TheoryDiscrete MathematicsTextbook