Network 1
max flow 5 = min cut 5
Cuts all have value 5.
In a network with capacities, the maximum flow from source to sink equals the minimum capacity of a cut separating from .
This page is easier if you are comfortable with:
A cut is a partition of the vertices into a set containing and a set containing ; its capacity is the total capacity of edges going from the first set to the second (the value of a cut). Consider (3), (2), (1), (2), (3). Send 2 along , 1 along and 2 along : then carries 3, total flow 5. The cut has capacity , so 5 is the maximum.
Another cut, against , has capacity , also minimal. In a second network ( 4, 1, 1, 2, 5), the flow is and the cut has capacity . Any flow is at most any cut, and the algorithm of augmenting paths finds equality, in the same spirit as linear programming duality.
Maximum flow solves matching problems: Hall's marriage theorem follows from it, and so do results on bipartite graphs. Shortest-path methods such as Dijkstra's relaxation step are the sibling problems for graphs.
The largest amount that can flow through a network equals the capacity of its narrowest cut.
The two edges out of s have capacities 3 + 2 = 5, equal to the flow.
These examples are worked by hand, step by step, so you can compare your own working.
Find the maximum flow when , , , , .
Find the capacity of the cut in that network.
For , , , , , find the maximum flow.
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
max flow 5 = min cut 5
Cuts all have value 5.
s→a 4, s→b 3, a→t 2, b→t 5, a→b 3
Flow: 2 via a→t, 2 via a→b→t, 3 via s→b→t.
a→t + b→t = 2 + 5 = 7
Equals the flow.
max flow = min cut
LP duality.
The maximum value of an s–t flow equals the minimum capacity of an s–t cut. Augmenting along paths with spare capacity increases the flow until no such path exists; the vertices reachable from s then define a minimum cut.
Network: s→a 4, s→b 3, a→t 2, b→t 5, a→b 3. Find a flow of value 7.
Find the value of the cut S = {s, a, b}.
What do the flow and cut values show?
Is the flow on b→t within capacity? It carries 2 + 3 = 5.
a flow of 5 is maximal ✗
check for augmenting paths ✓
An augmenting path means more is possible.
inflow ≠ outflow at a ✗
inflow = outflow ✓
Flow conservation.
flow 6 on b→t ✗
flow ≤ capacity 5 ✓
Respect capacities.
cut value 9 ✗
the minimum is 7 ✓
Search all cuts.
Try each one on paper, then open the answer. Use the solver above to see the full working.
7
7
9
2
0
7
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
The largest flow equals the smallest cut capacity.
Keep augmenting along paths with spare capacity.
Take vertices reachable from s in the residual graph.
Inflow equals outflow at every inner vertex.
value of a cut.
Hall’s marriage theorem.
More in Discrete maths and number theory and the formula sheets.