Maximum flow and minimum cut: VCE General Mathematics Unit 4 Networks and decision mathematics

Syllabus dot point

“Model a directed capacitated network with a source and sink, find the maximum flow from source to sink, identify cuts and their capacities, and use the minimum cut to confirm the maximum flow”

14 min readUpdated 23 Sep 2026

Quick answer

In a directed network with edge capacities, flow leaves the source and arrives at the sink, and at every other vertex flow in equals flow out. A path carries at most its smallest capacity. A cut divides the vertices into a source side and a sink side; its capacity is the sum of the capacities of edges directed from the source side to the sink side (edges pointing back are ignored). Every cut is an upper bound on the flow, and the maximum flow equals the capacity of the minimum cut. Find a flow and a cut with the same value and you have proved the maximum.

Jump to a section

What this dot point is asking
The answer
Flow in context
Exam-style questions
Practice questions

What this dot point is asking

Under "Flow problems" the Study Design lists "use of networks to model flow problems: capacity, sinks and sources" and "solution of small-scale network flow problems by inspection and the use of the 'maximum-flow minimum-cut' theorem to aid the solution of larger scale problems". You need to:

read a directed network where each edge has a capacity, with a source and a sink;
find a maximum flow by inspection;
calculate the capacity of a cut, counting only edges from the source side to the sink side;
use the maximum-flow minimum-cut theorem to find or confirm the maximum flow, and to decide which change to a network would increase it.

Flow appears every year, usually as a pair of multiple-choice questions on one network. In 2025 Examination 1 Questions 36 and 37 asked for the capacity of a drawn cut ( $77\%$ ) and the maximum flow ( $73\%$ ). In 2023 Examination 1 Questions 39 and 40 asked for the minimum cut ( $62\%$ ) and which change would most increase the flow (only $40\%$ ).

The answer

Capacity, source and sink

A flow network is a directed graph (a digraph with weights). Each edge has a capacity: the most that can pass along it per unit of time (litres per minute, cars per hour, children per minute). The source is where the flow starts and the sink is where it finishes.

A flow assigns an amount to each edge so that:

no edge carries more than its capacity, and nothing flows against an edge's direction;
at every vertex other than the source and sink, flow in = flow out (nothing is stored or lost).

The value of the flow is the total leaving the source, which equals the total arriving at the sink. The maximum flow is the largest possible value.

Bottlenecks: series and parallel

A single path carries at most its smallest capacity (the bottleneck): pipes of 10, 6 and 8 in series carry 6. Separate paths in parallel add. In a real network the paths share edges, so you cannot simply add the bottlenecks of every path; you must keep track of how much of each shared edge has been used.

Finding a maximum flow by inspection

For the small networks in VCE:

choose a path from source to sink and send its bottleneck amount along it;
reduce the remaining capacity of each edge on that path;
repeat with another path that still has spare capacity on every edge;
stop when every path from source to sink is blocked by a full edge.

A flow built this way is not guaranteed to be maximal (an early choice can block a better combination), so always confirm it with a cut of the same capacity.

Cuts and their capacity

A cut splits the vertices into two groups, one containing the source and the other containing the sink, so that every path from source to sink crosses from one group to the other. On paper it is drawn as a line through the edges.

The capacity of a cut is the sum of the capacities of the edges that cross it from the source side to the sink side. Edges that cross from the sink side back to the source side are not counted, because flow along them cannot help flow reach the sink.

The maximum-flow minimum-cut theorem

Every unit of flow must cross every cut, so the flow can never exceed the capacity of any cut. The theorem says the smallest cut is always achievable:

\text{maximum flow} = \text{capacity of the minimum cut}.

This gives a clean proof strategy for any flow question: find a flow of value $F$ and a cut of capacity $F$ . Then no flow can be larger (because of the cut) and $F$ is achieved (because of the flow), so $F$ is the maximum.

Good cuts to try first:

around the source (all edges leaving it);
around the sink (all edges entering it);
through the narrowest part of the network (small capacities, or a single vertex that everything must pass through).

Which change increases the flow?

Increasing the capacity of an edge only helps if that edge is in every minimum cut, and even then the flow can only rise until the next smallest cut becomes the limit. Reversing an edge can help a lot if it opens a new route from a vertex with surplus flow to one with spare capacity. In multiple choice, recalculate the maximum flow for each option (2023 Examination 1 Question 40).

Formula

Path capacity $=$ the smallest capacity on the path. Cut capacity $=$ sum of capacities of edges from the source side to the sink side (ignore edges pointing back). Any flow $\le$ any cut. Maximum flow $=$ minimum cut capacity.

Worked examples: cuts, maximum flows and changes

Capacity of a drawn cut (2025 Examination 1 Question 36)

Step 1: identify the two sides: Cut 1 puts the source, P, T, U and B on the source side, and M, R and the sink on the sink side.
Step 2: list every edge the cut crosses and its direction: U to sink 7 (forward), T to M 3 (forward), P to M 5 (forward), B to R 12 (forward), M to U 4 (backward), M to B 6 (backward).
Step 3: add the forward edges: $7 + 3 + 5 + 12 = 27$ . Answer: A.

The maximum flow in the same network (2025 Examination 1 Question 37)

Step 1: an easy cut. The three edges into the sink have capacities 7, 4 and 6: capacity 17. The maximum flow is at most 17.

Step 2: build a flow of 17.

source-T-U-sink: 7 (fills U to sink).
source-T-M-sink: 3 (T now sends $7 + 3 = 10$ of its 19).
source-P-M-sink: 1 (fills M to sink with $3 + 1 = 4$ ).
source-P-B-R-sink: 6 (fills R to sink; source to P now carries 7, its capacity).

Step 3: conclude. A flow of 17 and a cut of 17: maximum flow 17 (B). Cut 1 (27) was a valid cut but not the minimum.

Finding the minimum cut in a maze (2023 Examination 1 Question 39)

Step 1: trace where flow can reach H: H receives from G (12), F (10) and E (8). F's only incoming edge is E to F (4). E receives only from C (4) and D (7), so at most 11 passes through E.
Step 2: choose the cut: Put $\{A, B, C, D, G\}$ on the source side. Forward edges: G to H 12, C to E 4, D to E 7. Backward edges F to G and F to C are not counted. Capacity 23.
Step 3: check a flow of 23 exists: A to G 12 and G to H 12; A to C 4 then C to E 4; A to D 7 then D to E 7; from E, 8 to H and 3 to F then F to H 3. Every capacity holds, and $12 + 8 + 3 = 23$ arrives at H. Answer: B.

Which change helps most? (2023 Examination 1 Question 40)

Step 1: see where the surplus is. Up to $12 + 10 = 22$ can reach G (A to G, and A to B to G, which is limited to 10 by A to B), but only 12 leaves it. F has 10 of capacity to H but receives only 4.

Step 2: test the options. Increasing G to H to 16 lets 4 more through (27). Reversing F to C into C to F gives F up to 6 more from C (29). Reversing F to G into G to F sends G's surplus to F, which can pass up to 10 to H: the flow rises to 30, an increase of 7. Increasing F to H does nothing, because F is short of input, not output. Answer: E.

Marker's note: $21\%$ chose C. Increasing the edge with the largest capacity into the sink is not the same as increasing the flow; test whether the extra capacity can actually be fed.

Common traps

Counting edges that point backwards across a cut: Only source side to sink side edges count (2025 Examination 1 Question 36: 27, not 37).
Adding the capacities out of the source: That total (26 in 2025 Question 37) is only an upper bound; the rest of the network may not be able to carry it.
Stopping at the first cut you find: Any cut is an upper bound. The maximum flow is the minimum cut, so test several, or find a flow that matches.
Drawing a line that is not a cut: It must separate the source from the sink completely: every path from source to sink has to cross it.
Assuming a bigger pipe always means more flow: An increase only helps if the edge is in every minimum cut and the extra flow can be supplied and taken away.
Letting flow go against an arrow: In a directed network flow only travels in the direction of the edge.

Exam technique

In multiple choice, write the capacity of the cut around the source and the cut around the sink first: the answer can be no larger than the smaller of the two, which often eliminates two options. For a drawn cut, mark each crossing edge with a tick (forward) or a cross (backward) before adding. To justify a maximum flow in a written answer, state a flow that achieves it and a cut with the same capacity.

Flow in context

Flow networks model anything that moves through connections with limited capacity: water through pipes, traffic along one-way streets, people through a building's corridors, data through a computer network. The minimum cut identifies the bottleneck: the set of connections to upgrade if more flow is needed. That is why exam questions pair "what is the maximum flow" with "which change would increase it".

Note

Imagine water flowing through pipes from a source to a sink. Each pipe can only carry so much. A chain of pipes carries no more than its narrowest pipe. A cut is a line that separates the source from the sink; all the water must cross it, so the water flow can be no bigger than the total of the pipes crossing the line in the forward direction. The smallest such total is exactly the most water the network can carry. To prove your answer, show a way to send that much water and a cut with that total.

Exam-style questions

Questions in the style of VCAA 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.

2025 VCAA Exam 1 Q36Past paper1 mark

The network shows the flow of water, in litres per minute, in a system of pipes connecting the source to the sink. [Directed edges, with the paper's unlabelled vertices named here: source to T 19, source to P 7, T to P 6, T to U 10, T to M 3, P to M 5, P to B 8, M to U 4, U to sink 7, M to sink 4, M to B 6, B to R 12, R to sink 6. Cut 1 separates source, P, T, U and B from M, R and sink.] What is the capacity of Cut 1? A. 27 B. 31 C. 33 D. 37

Show worked answer →

Add only the edges that cross Cut 1 from the source side to the sink side:

U to sink: 7
T to M: 3
P to M: 5
B to R: 12

Capacity $= 7 + 3 + 5 + 12 =$ 27, option A ( $77\%$ ).

M to U (4) and M to B (6) also cross the cut, but they flow from the sink side back to the source side, so they are not counted. Adding them gives $27 + 4 + 6 = 37$ , option D ( $7\%$ ); adding just one of them gives 31 or 33.

Source: VCAA 2025 General Mathematics Examination 1, Question 36, and the 2025 examination report.

2025 VCAA Exam 1 Q37Past paper1 mark

For the same network of pipes (source to T 19, source to P 7, T to P 6, T to U 10, T to M 3, P to M 5, P to B 8, M to U 4, U to sink 7, M to sink 4, M to B 6, B to R 12, R to sink 6), what is the maximum flow of water, in litres per minute, from source to sink? A. 16 B. 17 C. 26 D. 30

Show worked answer →

Upper bound from a cut. The cut around the sink crosses U to sink (7), M to sink (4) and R to sink (6): capacity $17$ . No flow can exceed any cut, so the maximum flow is at most 17.

A flow that reaches it. Send 7 along source-T-U-sink, 3 along source-T-M-sink, 1 along source-P-M-sink and 6 along source-P-B-R-sink. Every capacity is respected (source to P carries $1 + 6 = 7$ ), and the total is $7 + 3 + 1 + 6 = 17$ .

A flow of 17 and a cut of 17 prove the maximum flow is 17, option B ( $73\%$ ). Option C (26) is the total leaving the source, which the rest of the network cannot carry.

Source: VCAA 2025 General Mathematics Examination 1, Question 37, and the 2025 examination report.

2023 VCAA Exam 1 Q39Past paper1 mark

The network shows the one-way paths between the entrance, A, and the exit, H, of a children's maze. The number on each edge is the maximum number of children allowed to travel along that path per minute. [A to B 10, A to G 12, A to C 10, A to D 8, B to G 15, G to H 12, F to G 10, F to H 10, F to C 6, C to E 4, D to C 5, D to E 7, E to F 4, E to H 8.] Cuts on this network are used to consider the possible flow of children through the maze. The capacity of the minimum cut would be A. 20 B. 23 C. 24 D. 29 E. 30

Show worked answer →

Everything reaching H comes from G (12), F (10) or E (8), but F's only way in is from E (4) and E's only ways in are C to E (4) and D to E (7).

So the cut separating $\{A, B, C, D, G\}$ from $\{E, F, H\}$ crosses G to H (12), C to E (4) and D to E (7): $12 + 4 + 7 = 23$ . F to C and F to G point back into the source side and are not counted.

A flow of 23 is possible (12 through G to H; 4 through C to E and 7 through D to E, with 3 of the 11 reaching H via F and 8 via E to H), so the minimum cut is 23, option B ( $62\%$ ).

Source: VCAA 2023 General Mathematics Examination 1, Question 39, and the 2023 examination report.

2023 VCAA Exam 1 Q40Past paper1 mark

For the children's maze in Question 39, one path in the maze is to be changed. Which one of these five changes would lead to the largest increase in flow from entrance to exit? A. increasing the capacity of flow along the edge CE to 12 B. increasing the capacity of flow along the edge FH to 14 C. increasing the capacity of flow along the edge GH to 16 D. reversing the direction of flow along the edge CF E. reversing the direction of flow along the edge GF

Show worked answer →

The current maximum flow is 23 (minimum cut G to H, C to E, D to E). Test each change:

A: C to E becomes 12. The new bottleneck gives 24, an increase of 1.
B: F to H becomes 14. F still only receives 4 from E: increase 0.
C: G to H becomes 16. Increase 4 (to 27).
D: C to F (6) gives a new route into F: increase 6 (to 29).
E: G to F (10) lets the surplus reaching G (up to 22 arrives, 12 from A and 10 via B, but only 12 leaves) flow on to F and then H: increase 7 (to 30).

Answer E. Only $40\%$ answered correctly; $21\%$ chose C. The report recommended inspecting the network and using the maximum-flow minimum-cut theorem.

Source: VCAA 2023 General Mathematics Examination 1, Question 40, and the 2023 examination report.

Practice questions

Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.

foundation2 marks

Two routes run from a source to a sink. Route 1 is a pipe of capacity 6 followed by a pipe of capacity 4. Route 2 is a pipe of capacity 5 followed by a pipe of capacity 7. The routes do not meet. Find the maximum flow and explain.

Show worked solution →

Pipes in series carry only the smallest capacity: route 1 carries $\min(6, 4) = 4$ and route 2 carries $\min(5, 7) = 5$ . (1 mark)

Separate routes in parallel add: maximum flow $= 4 + 5 = 9$ . (1 mark) Check with a cut through the 4-pipe and the 5-pipe: capacity 9.

foundation2 marks

A cut crosses four edges with capacities 8, 5, 6 and 3. The edge of capacity 6 is directed from the sink side to the source side; the others are directed from the source side to the sink side. (a) Find the capacity of the cut. (b) What does this tell you about the maximum flow?

Show worked solution →

(a) Count only the forward edges: $8 + 5 + 3 = 16$ . (1 mark)

(b) The maximum flow is at most 16. It equals 16 only if this is a minimum cut. (1 mark)

core3 marks

A directed network has capacities S to A 8, S to B 5, A to C 6, A to B 3, B to D 7, C to T 5 and D to T 9. (a) Find the capacity of the cut separating

\{S, A\}

from

\{B, C, D, T\}

. (b) Find the maximum flow from S to T and prove it with a cut.

Show worked solution →

(a) Forward edges: S to B 5, A to C 6, A to B 3. Capacity $= 14$ . (1 mark)

(b) Route through C: S-A-C-T carries at most $\min(8, 6, 5) = 5$ . Route through D: B receives at most $5 + 3 = 8$ (from S and A), but B to D is only 7, so 7 reaches T. Send 5 on S-B-D-T and 2 on S-A-B-D-T. A now carries $5 + 2 = 7 \le 8$ . Total flow $= 5 + 7 = 12$ . (1 mark)

The cut separating $\{S, A, B, C\}$ from $\{D, T\}$ crosses C to T (5) and B to D (7): capacity 12. A flow of 12 equals a cut of 12, so the maximum flow is 12. (1 mark)

core2 marks

A network has capacities S to A 9, S to B 6, A to B 4, A to C 5, B to C 3, B to D 7, C to T 8, D to C 2 and D to T 6. Find the maximum flow from S to T.

Show worked solution →

The cut around T crosses C to T (8) and D to T (6): capacity 14. Other cuts are larger: around S, $9 + 6 = 15$ ; separating $\{S, A, B\}$ , A to C 5, B to C 3 and B to D 7 give 15. (1 mark)

A flow of 14 is possible: S-A-C-T 5, S-B-C-T 3, S-B-D-T 3, S-A-B-D-T 3. Check B to D carries $3 + 3 = 6 \le 7$ . So the maximum flow is 14. (1 mark)

exam2 marks

In the previous network, the capacity of C to T is increased from 8 to 11. Find the new maximum flow and explain why it does not increase by 3.

Show worked solution →

The sink cut becomes $11 + 6 = 17$ , but two other cuts have capacity 15 (the cut around S, and the cut separating $\{S, A, B\}$ from $\{C, D, T\}$ ). They are now the minimum, so the new maximum flow is 15, an increase of only 1. (2 marks: 1 for 15, 1 for identifying the new minimum cut.)

exam2 marks

A student says a line drawn through the network crosses edges with total forward capacity 11, so the maximum flow is 11. Give two reasons why this conclusion might be wrong.

Show worked solution →

The line may not be a valid cut: it must separate the source from the sink so that every source-to-sink path crosses it. (1 mark)
A valid cut only gives an upper bound. The maximum flow equals the minimum cut, so 11 is the maximum flow only if no cut has a smaller capacity (or a flow of 11 can actually be found). (1 mark)

Practise this

Sources & how we know this

VCE General Mathematics Examination 1 (2023) and examination report — VCAA (2023)
VCE General Mathematics Examination 1 (2025) and examination report — VCAA (2025)
VCE Mathematics Study Design: General Mathematics (from 2023) — VCAA
VCE General Mathematics: examination specifications, past examinations and reports — VCAA