Max-flow min-cut Theorem Explained with Worked Examples

In a network with capacities, the maximum flow from source to sink equals the minimum capacity of a cut separating from .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Max-flow min-cut theorem means

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.

What is it used for?

The largest amount that can flow through a network equals the capacity of its narrowest cut.

How to use max-flow min-cut theorem

  1. Find a path from to with spare capacity and push flow.
  2. Repeat with the residual capacities until no path exists.
  3. The total flow is the maximum.
  4. Verify with a cut of equal capacity.

Graph

Edge capacities in the example network; the maximum flow is 5s→a: 3s→b: 2a→b: 1a→t: 2b→t: 3012345600.511.522.533.54Edge capacities in the example network; the maximum flow is 5edgeyGraph with x from 0 to 6 and y from 0 to 4. Shows bars (5); point s→a: 3 at (1, 3); point s→b: 2 at (2, 2); point a→b: 1 at (3, 1); point a→t: 2 at (4, 2); point b→t: 3 at (5, 3).

The two edges out of s have capacities 3 + 2 = 5, equal to the flow.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: maximum flow

Find the maximum flow when , , , , .

Worked example
Answer
55
  1. Flow

Example 2: a matching cut

Find the capacity of the cut in that network.

Worked example
Answer
55
  1. Edges out of s

Example 3: a second network

For , , , , , find the maximum flow.

Worked example
Answer
44
  1. Cut {s,a}

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Network 1

max flow 5 = min cut 5

Cuts all have value 5.

Network 2

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.

Min cut

a→t + b→t = 2 + 5 = 7

Equals the flow.

Duality

max flow = min cut

LP duality.

Word problems

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.

A flow

Network: s→a 4, s→b 3, a→t 2, b→t 5, a→b 3. Find a flow of value 7.

  1. s→a→t2
  2. s→a→b→t2
  3. s→b→t3
  4. Check: total 7 ✓7.

A cut

Find the value of the cut S = {s, a, b}.

  1. a→t2
  2. b→t5
  3. Check: 7 ✓7.

The theorem Higher

What do the flow and cut values show?

  1. 7 = 7
  2. Check: the flow is maximum and the cut minimum ✓Max flow = min cut = 7.

Check capacities Higher

Is the flow on b→t within capacity? It carries 2 + 3 = 5.

  1. 5 ≤ 5
  2. Check: saturated ✓Yes.

Common mistakes

Stopping early

a flow of 5 is maximal ✗

check for augmenting paths ✓

An augmenting path means more is possible.

Ignoring conservation

inflow ≠ outflow at a ✗

inflow = outflow ✓

Flow conservation.

Exceeding capacity

flow 6 on b→t ✗

flow ≤ capacity 5 ✓

Respect capacities.

Taking a non-minimal cut

cut value 9 ✗

the minimum is 7 ✓

Search all cuts.

Exam tips

  1. Max flow = min cut.
  2. Augmenting paths.
  3. Conservation at inner vertices.
  4. Saturated edges form the cut.
  5. Check both values.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Flow 3 + 4 Foundation

7

2. Cut with edges 2, 5 Foundation

7

3. Max flow if min cut is 9 Foundation

9

4. Spare capacity: 5 − 3 Higher

2

5. Inflow 4, outflow 2 + 2 Higher

0

6. Total capacity 4 + 3 Higher

7

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Flow
Assignment of amounts to edges.
Capacity
Edge limit.
Augmenting path
Path with spare capacity.
Min cut
Cut of least capacity.
Conservation
Inflow = outflow.
Residual graph
Remaining capacities.

Frequently asked questions

What does the max-flow min-cut theorem say?

The largest flow equals the smallest cut capacity.

How do I find the max flow?

Keep augmenting along paths with spare capacity.

How do I find the min cut?

Take vertices reachable from s in the residual graph.

What is flow conservation?

Inflow equals outflow at every inner vertex.

Which page covers the value of a cut?

value of a cut.

Which page covers Hall’s theorem?

Hall’s marriage theorem.

More in Discrete maths and number theory and the formula sheets.