12.8 Max-Flow Min-Cut Theorem

Problem

A maximum-flow algorithm returns a number. That number tells you how much flow can be sent from the source to the sink.

But an algorithmic answer alone is not enough. You also need a reason why the answer is optimal.

Suppose an algorithm returns:

maximum flow = 37

How do you know that 38 is impossible?

A minimum cut provides the certificate. The max-flow min-cut theorem explains why the certificate is valid.

Solution

The max-flow min-cut theorem states:

In every flow network, the value of the maximum flow equals the capacity of the minimum cut.

That is:

maximum flow value = minimum cut capacity

This theorem connects two different views of the same network.

Flow view:

How much can pass through the network?

Cut view:

What is the smallest bottleneck separating source from sink?

The theorem says these answers are identical.

Definitions

Let:

G = (V, E)

be a directed flow network with source:

and sink:

Each edge has capacity:

c(u, v)

A flow assignment:

f(u, v)

must satisfy capacity and conservation constraints.

A cut is a partition:

(A, B)

such that:

s ∈ A
t ∈ B
A ∪ B = V
A ∩ B = ∅

The capacity of the cut is:

sum of c(u, v)
over all u ∈ A and v ∈ B

Only edges from the source side to the sink side count.

Weak Duality

The first fact is simple and extremely useful:

Every feasible flow is less than or equal to every cut capacity.

In symbols:

|f| ≤ c(A, B)

Why?

Any unit of flow that starts at s and ends at t must cross from A to B at some point. The total amount crossing from A to B cannot exceed the total capacity of edges from A to B.

So every cut is an upper bound on every flow.

This means:

any flow value ≤ any cut capacity

If you ever find a flow and a cut with the same value, both are optimal.

Example

Consider:

Edge	Capacity
s -> a	10
s -> b	5
a -> t	8
b -> t	10

A feasible flow:

Edge	Flow
s -> a	10
s -> b	5
a -> t	8
b -> t	7

The flow value is:

The cut:

A = {s}
B = {a, b, t}

has capacity:

10 + 5 = 15

Therefore:

maximum flow = minimum cut = 15

No larger flow can exist.

The Strong Statement

Weak duality gives only this:

maximum flow ≤ minimum cut

The theorem proves the stronger fact:

maximum flow = minimum cut

To prove equality, it is enough to show that when an augmenting-path algorithm terminates, it produces a cut whose capacity equals the current flow value.

Residual Reachability

Assume a maximum-flow algorithm has terminated.

That means there is no augmenting path from s to t in the residual graph.

Now compute:

A = all vertices reachable from s in the residual graph

Since no augmenting path exists:

t ∉ A

Let:

B = V - A

Then (A, B) is a valid cut.

The key step is to inspect edges crossing this cut.

Forward Edges Are Saturated

Take any original edge:

u -> v

where:

u ∈ A
v ∈ B

If this edge had unused residual capacity, then v would be reachable from s.

But v is not in A.

Therefore the edge has no residual capacity.

So:

f(u, v) = c(u, v)

Every forward edge from A to B is saturated.

Backward Edges Carry No Flow

Now take any original edge:

v -> u

where:

v ∈ B
u ∈ A

If this edge carried positive flow, the residual graph would contain a reverse edge:

u -> v

with positive residual capacity.

Then v would be reachable from s.

But v is not in A.

Therefore:

f(v, u) = 0

Every backward edge from B to A carries zero flow.

Equality

The value of the flow equals the net flow crossing any s-t cut.

For the cut (A, B):

flow value
=
flow from A to B
-
flow from B to A

From the two facts above:

flow from A to B = capacity(A, B)

and:

flow from B to A = 0

Therefore:

flow value = capacity(A, B)

Since every flow is bounded above by every cut, equality proves both optimality statements:

current flow is maximum

and:

current cut is minimum

Algorithmic Consequence

The theorem gives a practical stopping rule:

Run a max-flow algorithm.
Stop when no augmenting path exists.
Compute vertices reachable from the source in the residual graph.
Extract cut edges from the original graph.
The flow value and cut capacity are equal.

This produces both:

an optimal solution
a certificate of optimality

The certificate is often as valuable as the number.

Why This Matters

In implementation work, the theorem explains what your algorithm is doing.

Ford-Fulkerson, Edmonds-Karp, and Dinic all repeatedly improve a flow using residual paths. When the residual graph no longer connects s to t, the reachable set from s defines a bottleneck whose capacity exactly equals the flow already achieved.

In modeling work, the theorem explains why flow problems are useful.

Many optimization problems can be solved by constructing a graph where a cut represents a decision boundary. Once the graph is built, finding a minimum cut gives the optimal decision.

Common Mistakes

Treating the theorem as only a graph fact

The theorem is also an algorithmic certificate. It tells you how to verify a maximum-flow result.

Computing the cut on the residual graph

The reachable set is computed on the residual graph. The cut capacity is computed using original capacities.

Counting both directions

For a directed cut, only original edges from A to B contribute to capacity.

Forgetting backward-flow cancellation

The proof depends on showing that edges from B to A carry zero flow when the algorithm terminates.

Takeaway

The max-flow min-cut theorem states that the largest feasible flow from source to sink equals the smallest capacity of any cut separating them.

This theorem gives maximum-flow algorithms their correctness proof. It also gives users a certificate: a flow and a cut with the same value prove that no better solution exists.