Flow networks, maximum flow and minimum cut (QCE General Mathematics Unit 4)
“Understand source node, sink node, cut, minimum cut and maximum flow, use a flow network diagram to identify a cut, determine the capacity of a cut, and solve small-scale practical problems involving flow networks (up to 8 possible cuts), including determining the minimum cut and the maximum flow”
A flow network is a directed graph with a source, a sink and a capacity on each edge; flow is conserved at every other vertex. A cut splits the vertices with the source on one side and the sink on the other, and its capacity is the sum of edges crossing from the source side to the sink side only. With intermediate vertices there are cuts; list them, and the smallest capacity is the maximum flow (maximum-flow minimum-cut theorem).
What this dot point is asking
A flow network models anything that moves through a system of one-way channels with limited capacity: water through pipes, cars through one-way streets, data through cables, people through turnstiles. The QCAA General Mathematics 2025 syllabus (Topic 5, Networks and decision mathematics 2) asks you to:
- understand the meaning of source node, sink node, cut, minimum cut and maximum flow;
- use a flow network diagram to identify a cut (and recognise a line that is not a valid cut);
- determine the capacity of a cut;
- solve small-scale practical problems (with up to 8 possible cuts), including finding the minimum cut and the maximum flow.
This is a four-hour sub-topic and a regular short-response item in the Unit 4 internal examination and the external assessment.
The answer
Flow networks
A flow network is a directed graph with:
- a source (the vertex where flow begins),
- a sink (the vertex where flow ends), and
- a capacity on each edge: the most that edge can carry per unit of time, in the direction of its arrow.
Two rules govern any flow:
- Capacity rule. The flow along an edge can be anything from 0 up to its capacity, never more. An edge carrying its full capacity is saturated.
- Conservation. At every vertex except the source and sink, flow in equals flow out. Water does not pile up or appear from nowhere at a junction.
Two quick consequences: pipes in series are limited by the smallest capacity along the route; separate routes that share no edge have flows that add.
Cuts and their capacities
A cut splits the vertices into two groups: a source side containing the source and a sink side containing the sink. On a diagram it is drawn as a line (it may bend) across the network. For the line to be a valid cut, every route from the source to the sink must cross it, so the source and the sink must end up on opposite sides.
The capacity of a cut is the total capacity of the edges it crosses from the source side to the sink side:
- edges pointing from the source side to the sink side are counted;
- edges pointing from the sink side back to the source side are not counted (they carry flow the wrong way across the cut).
In the network above, the cut with source side {S, B} and sink side {A, C, T} crosses S to A (9), A to B (3) and B to C (6). But A to B points from A (sink side) into B (source side), so it is not counted. The capacity is .
A cut separates the source from the sink. Its capacity is the sum of the capacities of the edges crossing it from the source side to the sink side only. Every cut capacity is an upper bound on the flow, and by the maximum-flow minimum-cut theorem the maximum flow equals the capacity of the minimum cut.
Listing every cut
With a small network you can find the minimum cut with certainty by listing all the cuts. Each vertex other than the source and sink can go on either side, so a network with 3 such vertices has cuts (the syllabus limit), 2 vertices give 4 cuts, and 1 vertex gives 2.
For the network above (other vertices A, B, C):
| Source side | Edges counted (source side to sink side) | Capacity |
|---|---|---|
| {S} | S to A 9, S to B 7 | 16 |
| {S, A} | S to B 7, A to B 3, A to C 5, A to T 4 | 19 |
| {S, B} | S to A 9, B to C 6 (A to B points back) | 15 |
| {S, C} | S to A 9, S to B 7, C to T 10 | 26 |
| {S, A, B} | A to C 5, A to T 4, B to C 6 | 15 |
| {S, A, C} | S to B 7, A to B 3, A to T 4, C to T 10 | 24 |
| {S, B, C} | S to A 9, C to T 10 (A to B and A to C point back) | 19 |
| {S, A, B, C} | A to T 4, C to T 10 | 14 |
The minimum cut is {S, A, B, C} | {T}, with capacity 14, so the maximum flow is 14.
The maximum-flow minimum-cut theorem
Why do the two numbers agree? All flow has to cross every cut, so no flow can be bigger than any cut: every cut capacity is a ceiling. The smallest ceiling is the minimum cut. The theorem says this smallest ceiling can always be reached: there is a flow that fills the edges of the minimum cut exactly.
For the network above, one maximum flow is:
- S to A 9, split into A to T 4 and A to C 5 (A to B carries 0);
- S to B 5 (of its 7), all along B to C;
- C to T .
Conservation holds at A (), B () and C (), and reaches T. The two edges of the minimum cut, A to T and C to T, are both saturated.
Maximum flow by inspection
For simple networks you can also build the maximum flow directly:
- Choose a route from source to sink with spare capacity on every edge.
- Send as much as the smallest spare capacity on that route allows.
- Reduce the spare capacity of each edge used.
- Repeat until no route has spare capacity on every edge. The total sent is the maximum flow.
Always confirm the answer with a cut of the same capacity: if you have found a flow of 14 and a cut of capacity 14, neither can be improved.
Practical questions
- "Which line is not a valid cut?" Look for a line that leaves the source and sink on the same side, or that some route can go around without crossing.
- "Find the capacity of each cut." Add the forward-crossing edges only; watch for arrows pointing back.
- "Find the maximum flow." List the cuts (up to 8), take the smallest, and quote the theorem.
- "A pipe is upgraded (or blocked)." Change that capacity and recalculate every cut containing that edge. If the upgraded edge is not on the minimum cut, nothing changes. If it is, the flow rises only until another cut becomes the minimum.
- "Which edges are saturated at maximum flow?" The edges of the minimum cut.
Capacity of a cut with a backward edge
In the network S to A 8, S to B 6, B to A 4, A to C 7, B to C 3, A to T 2, C to T 9, find the capacity of the cut {S, A} | {B, C, T}.
Edges crossing. S to B (6), A to C (7), A to T (2) cross forward. B to A crosses backward (from B on the sink side into A on the source side).
Capacity. .
Marker's note: circle each crossing edge on the diagram and write F (forward) or B (backward) beside it before adding.
Maximum flow by listing all cuts
Same network: S to A 8, S to B 6, B to A 4, A to C 7, B to C 3, A to T 2, C to T 9. Find the maximum flow.
- List the 8 cuts (source side)
- {S} 14; {S, A} 15; {S, B} 15 (S to A 8, B to A 4, B to C 3); {S, C} 23; {S, A, B} 12 (A to C 7, B to C 3, A to T 2); {S, A, C} 17; {S, B, C} 21; {S, A, B, C} 11 (A to T 2, C to T 9).
- Minimum
- 11, from {S, A, B, C} | {T}.
- Answer
- Maximum flow 11. A flow achieving it: S to A 6, S to B 5, B to A 2, B to C 3, A to T 2, A to C 6, C to T 9.
Marker's note: show that conservation holds for your flow (at A: in , out ) if the question asks you to demonstrate it.
When the bottleneck is at the source
Pipes: S to A 8, S to B 5, A to T 6, B to T 9. Find the maximum flow.
Routes. S-A-T carries at most 6; S-B-T at most 5. They share no pipe, so the total is 11.
Confirm. Cut {S, A} | {B, T}: S to B 5, A to T 6, capacity 11. The flow equals a cut, so 11 is the maximum.
Marker's note: the bottleneck here mixes one pipe from the source and one pipe into the sink. Only listing cuts reliably finds mixed bottlenecks.
An upgrade question
In the S, A, B, C, T network above (maximum flow 14), pipe A to T is upgraded from 4 to 8. Find the new maximum flow.
- Recalculate cuts containing A to T
- {S, A}: 23. {S, A, C}: 28. {S, A, B}: 19. {S, A, B, C}: 18.
- Other cuts unchanged
- {S} 16, {S, B} 15, {S, C} 26, {S, B, C} 19.
- New minimum
- 15, from {S, B} | {A, C, T}. The maximum flow increases only from 14 to 15.
Marker's note: an upgrade of 4 gave an increase of 1 because a different cut became the bottleneck. Examiners like this "explain why" follow-up.
- Counting backward edges
- An edge pointing from the sink side to the source side contributes 0 to the cut's capacity.
- Missing cuts
- Checking only the cuts around the source and the sink misses bottlenecks in the middle. List all cuts for intermediate vertices.
- Accepting an invalid cut
- A line that leaves the source and sink on the same side, or that a route can go around, is not a cut.
- Adding bottlenecks of routes that share an edge
- Two routes through the same pipe cannot each use its full capacity.
- Quoting the minimum of only the drawn cuts as the maximum flow
- Unless you have checked every cut, the smallest drawn cut is only an upper bound.
- Ignoring arrow directions when pushing flow
- Flow can only travel in the direction of each arrow.
When asked for a maximum flow, present a table of cuts: source-side vertices, the forward edges crossed, and the capacity. Circle the minimum and write "by the maximum-flow minimum-cut theorem, maximum flow minimum cut ...". If there is time, give a flow on each edge that achieves the maximum, which proves the answer from both sides. State units (kL per minute, cars per hour).
Think of water pipes from a tank to a tap, each pipe with a limit on how much it can carry. The most water that can reach the tap is set by the tightest squeeze somewhere in the system. To find that squeeze, imagine slicing across the pipes so the tank is on one side and the tap is on the other, and add up the limits of the pipes you cut that carry water towards the tap. Try every possible slice; the smallest total is exactly the most water that can get through.
Exam-style questions
Questions in the style of QCAA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.
Practice4 marksThe network diagram shows the flow of water from the tank (source) to the kitchen tap (sink), with four dashed lines L1, L2, L3 and L4 drawn across it. a) Explain which dashed line (L1, L2, L3 or L4) is not a valid cut. [1 mark] b) Calculate the capacity of each dashed line that is a valid cut. [3 marks] (L1 crosses edges of capacity 20, 22, 15; L2 crosses 18, 19, 22, 15; L3 crosses 18, 8, 10.)Show worked answer →
a) Invalid cut (1 mark). A valid cut must completely separate the source from the sink: every route from the tank to the tap must cross it, with the tank on one side and the tap on the other. In the examination diagram, L4 does not do this (the tank and the tap end up on the same side, so water could reach the tap without crossing L4). It is not a valid cut.
b) Capacities of the valid cuts (3 marks). A cut's capacity is the sum of the capacities of the edges it crosses in the direction from the source side to the sink side; an edge pointing back from the sink side to the source side counts as 0.
- L1: (1 mark)
- L2: (1 mark)
- L3: (1 mark)
All three edges listed for each cut are counted in the original question, so they all point from the source side to the sink side. Of these three cuts, L3 has the smallest capacity, so the maximum flow can be at most 36. It equals 36 only if no other cut in the whole network has a smaller capacity: the maximum-flow minimum-cut theorem uses the minimum over all cuts, not just the ones drawn.
Modelled on the QCAA 2021 General Mathematics external assessment (not checked word for word against the paper) (question text summarised; the diagram is not reproduced).
Practice questions
Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.
foundation2 marksPipes carry water (kL per minute) from source S to sink T: S to A 8, S to B 5, A to T 6, B to T 9. (a) Find the capacity of the cut that separates {S} from {A, B, T}. (b) Find the maximum flow.
Show worked solution →
(a) The cut crosses S to A (8) and S to B (5): capacity . (1 mark)
(b) The two routes do not share any pipe. Route S-A-T is limited by and route S-B-T by , so the maximum flow is kL per minute. (1 mark) Check with the cut {S, A} | {B, T}: it crosses S to B (5) and A to T (6), capacity 11, equal to the flow.
foundation1 markWhich one of the following is **not** required of a valid cut in a flow network? A. The source is on one side and the sink is on the other. B. Every route from source to sink crosses it. C. It crosses only edges that point from the source side to the sink side. D. It divides the vertices into two groups.
Show worked solution →
C. A valid cut may cross edges pointing in either direction; edges pointing from the sink side back to the source side are simply not counted in its capacity. A, B and D are all required.
foundation2 marksA cut crosses three edges: one of capacity 12 pointing from the source side to the sink side, one of capacity 7 pointing from the source side to the sink side, and one of capacity 5 pointing from the sink side to the source side. Find the capacity of the cut and explain.
Show worked solution →
Only edges crossing from the source side to the sink side count: . (1 mark)
The edge of capacity 5 carries flow back towards the source side, so it cannot help flow get from the source to the sink across this cut; it contributes 0. (1 mark)
core3 marksA network has edges S to P 12, S to Q 8, P to Q 4, P to R 6, Q to R 9, P to T 5, Q to T 3 and R to T 11. (a) How many different cuts are there? (b) Find the capacity of the cut {S, P} | {Q, R, T}. (c) Find the maximum flow and the minimum cut.
Show worked solution →
(a) There are 3 vertices other than S and T (P, Q, R); each can be on the source side or the sink side, so there are cuts. (1 mark)
(b) Edges from {S, P} to {Q, R, T}: S to Q 8, P to Q 4, P to R 6, P to T 5. Capacity . (1 mark)
(c) Listing all eight cuts gives capacities 20 ({S}), 23 ({S, P}), 24 ({S, Q}), 31 ({S, R}), 23 ({S, P, Q}), 28 ({S, P, R}), 26 ({S, Q, R}) and 19 ({S, P, Q, R}). The minimum is 19, the cut {S, P, Q, R} | {T} crossing P to T (5), Q to T (3) and R to T (11). So the maximum flow is 19. (1 mark)
core3 marksFor the network S to A 9, S to B 7, A to B 3, A to C 5, A to T 4, B to C 6, C to T 10, give a flow along every edge that achieves the maximum flow of 14, and check conservation of flow at A, B and C.
Show worked solution →
One maximum flow: S to A 9, A to T 4, A to C 5, A to B 0; S to B 5, B to C 5; C to T 10. (2 marks)
Conservation: at A, in 9 and out ; at B, in and out 5; at C, in and out 10. Into T: . (1 mark) Every edge is at or below its capacity (S to B carries 5 of its 7).
core2 marksIn the network S to A 8, S to B 6, B to A 4, A to C 7, B to C 3, A to T 2, C to T 9, find the capacity of the cut {S, A} | {B, C, T}.
Show worked solution →
Edges from {S, A} to the sink side: S to B (6), A to C (7), A to T (2). The edge B to A points from the sink side (B) back to the source side (A), so it is not counted. (1 mark)
Capacity . (1 mark)
exam4 marksFor the network S to A 9, S to B 7, A to B 3, A to C 5, A to T 4, B to C 6, C to T 10 (maximum flow 14), the council plans to upgrade pipe A to T from capacity 4 to capacity 8. (a) Find the new maximum flow. (b) Explain why the increase is less than 4. (c) Could any single pipe upgrade (of any size) raise the maximum flow of the original network to 16? Explain.
Show worked solution →
(a) Recalculate the cuts with A to T = 8. The cut {S, A, B, C} | {T} rises to , but the cut {S, B} | {A, C, T} is still (S to A and B to C; A to B points backwards). The minimum is now 15, so the new maximum flow is 15. (2 marks)
(b) Before the upgrade the bottleneck was the pair of pipes into T (4 + 10). Raising A to T moves the bottleneck to another cut, {S, B} | {A, C, T}, which has capacity 15. Flow can only rise to the next-smallest cut. (1 mark)
(c) No. A flow of 16 needs every cut to have capacity at least 16, and three cuts are below 16: {S, B} (15: S to A, B to C), {S, A, B} (15: A to C, A to T, B to C) and {S, A, B, C} (14: A to T, C to T). No single pipe belongs to all three of these cuts (B to C is in the first two but not the third; A to T is in the last two but not the first), so upgrading one pipe always leaves at least one cut below 16. At least two upgrades are needed, for example B to C to 7 and A to T to 6, after which every cut is at least 16. (1 mark for a justified conclusion.)
exam2 marksExplain why the capacity of every cut is an upper bound for the flow, and why the minimum cut gives the maximum flow.
Show worked solution →
Every unit of flow travels from the source to the sink, so it must cross any line that separates them, and it can only cross along edges pointing from the source side to the sink side. So the total flow can never exceed the sum of those edges' capacities: every cut capacity is an upper bound. (1 mark)
The tightest (smallest) of these bounds is the minimum cut, and the maximum-flow minimum-cut theorem states that this bound can always be achieved: some flow fills the minimum cut's edges exactly. So the maximum flow equals the minimum cut capacity. (1 mark)