Topic guide 14 · Unit 4 Topic 5 · Networks and decision mathematics 2
Flow networks
A flow network is a directed graph whose edges have capacities: litres per second through a pipe, vehicles per hour along a road, tonnes a day of supplies. Flow leaves the source, follows the arrows and arrives at the sink. Every question asks some version of how much can get through, and the answer is the capacity of the smallest cut.
The QCAA set a flow question in four of the six exams from 2020 to 2025, and every one of them is reproduced and marked below. This guide teaches you to check that a cut is valid, find its capacity without the backward edges, list every cut so the minimum has nowhere to hide, and handle the questions that change the network after you have found the answer. Tick off each skill once you can do it without help.
19
marks on flow networks in five questions, 2020 to 2025
36.9%
of students picked the minimum cut in 2021 Paper 1 Question 7
8
possible cuts at most in a syllabus flow problem, so you can list them all
Skills in this topic
Only tick a skill when you could do it in the exam. Your ticks are saved in this browser only.
Part 1
What the exam asks about flow networks
Flow networks share Unit 4 Topic 5 with the Hungarian algorithm. Together the two halves carried 45 short-response marks across the six external exams from 2020 to 2025, and the topic appeared in all six years. The assignment half has its own guide, Assignment and the Hungarian algorithm.
I count five questions on flow networks, worth 19 marks: 2020 Paper 1 Question 21, 2021 Paper 1 Questions 7 and 23, 2023 Paper 1 Question 21 and 2025 Paper 2 Question 3. Four are short response and one is multiple choice. That multiple choice question, which asked for the minimum cut among four drawn cuts, was answered correctly by only 36.9% of the state.
Question
Marks
What it tests
2020 P1 Q21
5
Cyclone shelter. All the cuts, maximum flow 90 tonnes, then vertex A is damaged and it drops to 70. Part 4
2021 P1 Q7 (MC)
1
Which of four valid cuts gives the maximum flow, meaning the minimum cut ($C_1 = 150$). 36.9% correct. Part 4
2021 P1 Q23
4
Which of $L_1$ to $L_4$ is not a valid cut, and the capacities of the valid ones (57, 74 and 36, with a backward edge left out). No maximum flow asked. Part 3
2023 P1 Q21
4
Capacity of cut X (440, with a backward 50 left out), maximum flow 300, then 120 with the bridge closed. Part 4
2025 P2 Q3
5
Build the network from a table, find the maximum flow (44, from two minimum cuts), then upgrade one pipe, C to E, to 25 L/sec for a flow of 45. Part 5
The subject reports name two habits. The 2020 report asked for the difference between minimum cut and maximum flow, and for the ‘maximum-flow minimum-cut’ theorem, which “requires the correct identification of all the possible cuts for a small-scale network flow problem”. The 2025 report chose a 2025 Paper 2 Question 3 response “to demonstrate an appropriate method that included finding all cuts and calculating the flow across each cut to identify the original maximum flow for the network”.
What the syllabus says
Unit 4 Topic 5 gives the sub-topic Flow networks 4 hours and four dot points:
•Understand the meaning of 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.
•Solve small-scale practical problems involving flow networks (up to 8 possible cuts), including determining the minimum cut and the maximum flow.
The bracket in the last dot point is the useful part. With at most eight cuts, you can write every one down and compare them. That is the method this guide teaches, and the one the subject reports showcase.
What changed in the 2025 syllabus
The 2019 syllabus gave flow networks 3 hours and one dot point on the ‘maximum-flow minimum-cut’ theorem. The 2025 syllabus names the terms, separates finding a cut from finding its capacity, and adds the limit of up to 8 possible cuts. The 2025 subject report lists that limit among the Unit 4 revisions.
The two 2021 questions use networks with five middle nodes, which allows far more than eight cuts, but both drew the cuts for you. Every past question that asked you to find the cuts yourself (2020, 2023 and 2025) has exactly eight.
The definitions and the theorem are yours to carry in. There are only five terms, and once the cuts are right the rest is addition.
Part 2
Five terms and the theorem that links them
Five terms come up in every flow question, and the first dot point asks you to understand all of them.
Term
Meaning
Source
The node where the flow starts. Nothing flows into it.
Sink
The node where the flow ends. Nothing flows out of it.
Cut
A line across the network that completely separates the source from the sink.
Capacity of a cut
The total capacity of the edges the cut crosses, counting only edges directed from the source side to the sink side.
Maximum flow
The largest amount that can travel from source to sink. It equals the capacity of the minimum cut, the cut with the smallest capacity.
The orange cut has S and B on the source side. It crosses S→A (9), A→B (4) and B→T (12), and A→B points back towards the source side. Animated: the four cuts in turn. Orange edges are counted, blue dashed edges point back and are not.
Look at the edges the orange cut crosses. S→A and B→T run from the source side to the sink side, so they count. A→B runs from A, on the sink side, back to B, on the source side. Flow along it cannot help anything reach T across this cut, so it is left out. The capacity is $9 + 12 = 21$.
This network has two middle nodes, A and B, so there are four cuts. Each one is fixed by which middle nodes sit on the source side:
Source side
Capacity
S
$9 + 7 = 16$
S, A
$7 + 4 + 6 = 17$
S, B A→B points back
$9 + 12 = 21$
S, A, B
$6 + 12 = 18$
The smallest is 16, so the minimum cut is the one around S and the maximum flow is 16. You can see a flow of 16 working: send 9 to A and 7 to B, pass 6 from A to T and 3 down A→B, and B sends $7 + 3 = 10$ to T, inside its 12.
Why the maximum flow equals the minimum cut
Every unit of flow leaving the source has to cross every cut on its way to the sink. No cut can pass more than its own capacity, so the flow can never exceed the smallest cut.
The theorem adds the other half: there is always a flow that fills the smallest cut exactly, so the maximum flow equals it rather than merely staying below it. That is why one list of cuts answers the question.
The 2020 report asked for the difference between minimum cut and maximum flow. The minimum cut is a set of edges, the bottleneck. The maximum flow is an amount, with units. They have the same number, and a full answer says both: “the minimum cut is 90, so the maximum flow is 90 tonnes per day”.
Part 3
A valid cut separates, and only forward edges count
The second and third dot points are about one cut at a time: is it a cut, and what is its capacity? Two rules settle both.
Rule 1 · A cut must separate the source from the sink
Every path from source to sink has to cross the line. If any path gets through without crossing it, the line is not a valid cut.
The quickest test is to say which nodes are on the source side. A valid cut has the source on one side and the sink on the other. A line that loops round a middle node and leaves source and sink together, like L4 in 2021, fails.
Rule 2 · Count only edges pointing from the source side to the sink side
A cut can cross an edge that runs backwards, from the sink side to the source side. That edge adds nothing to the capacity, so leave it out.
Check the arrow on every edge your line crosses. In 2021 Question 7, 2021 Question 23 and 2023 Question 21 a backward edge sits on a cut drawn for you, and 2020 and 2025 have backward edges on several of the cuts you list yourself.
A cut can cross the network in a curve and does not have to be a straight line. What matters is which side each node ends up on.
2021 Paper 1 Question 23
Paper 1 · Simple familiar · [4 marks]
The network diagram shows the flow of water from the tank (source) to the kitchen tap (sink).
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]
a) L4 curves round B and comes back out above the tap. The tank and the tap are both outside it, on the same side. Water can still go Tank → D → E → Tap without crossing L4 at all.
1 mark · correctly explains why L4 is not a valid cut
The guide’s answer is “L4 is not valid because the tank and the tap are on the same side of the line”, and it accepts equivalent statements. Naming the open path is one.
b) For each valid line, list the nodes on the tank side, then add the edges that leave that side.
L1 has only the tank on its side. It crosses Tank→A, Tank→C and Tank→D:
$$L_1 = 20 + 22 + 15 = 57$$
1 mark · correctly determines the L1 capacity
L2 has the tank, A and D on its side. It crosses A→B (18), A→C (19), Tank→C (22), D→E (15) and C→D (16). The 16 runs from C, on the tap side, to D, on the tank side, so it is left out:
The orange edge, C→D, crosses L₂ towards the tank side, so its 16 is not counted.
L3 has the tank, A, C, D and E on its side. It crosses A→B, C→B and E→Tap. C→E does not cross it, since C and E are on the same side:
$$L_3 = 18 + 8 + 10 = 36$$
1 mark · correctly determines the L3 capacity
Counting the backward 16 makes L2 90, which is the slip this question is built to catch.
The question stops at the capacities. If it had asked for the maximum flow, you would need every cut, including ones nobody drew. The cut through B→Tap and E→Tap alone is $17 + 10 = 27$, smaller than all three dashed lines, and the maximum flow is 27. A single cut only tells you the flow can be no bigger than its capacity. The smallest cut is the one that gives the maximum.
Answer
a) L4 · b) L1 = 57, L2 = 74, L3 = 36
Part 4
List every cut, then take the smallest
The fourth dot point asks for the minimum cut and the maximum flow. With at most eight cuts, the reliable method is to list them all.
1Identify the source and the sink.
2List every cut that separates them. The 2025 syllabus sets a limit of eight for these problems.
3For each cut, write the edges it crosses from the source side to the sink side, then total their capacities.
4Name the smallest total as the minimum cut, and state that the maximum flow equals it, with units.
A system that finds every cut
Every cut splits the nodes into a source side and a sink side. The source is always on one side and the sink always on the other. Each middle node can go either way, so three middle nodes give $2 \times 2 \times 2 = 8$ cuts.
Write the source sides in order. For middle nodes A, B and C: {S}, {S, A}, {S, B}, {S, C}, {S, A, B}, {S, A, C}, {S, B, C}, {S, A, B, C}. Then for each one, add up the edges that leave it. This finds the awkward cuts that are hard to draw as a single curve, which are the ones people miss.
Show every cut, not just the winner
Writing only the minimum cut asserts an answer without showing it. A marker cannot tell whether you found the smallest or guessed it.
A short table of source sides against capacities is enough, and it is where the method marks are. 2020 Question 21 gave one mark for identifying all the cuts and another for calculating the flow across all of them.
Valid cuts and the minimum cut
2021 Paper 1 Question 7 drew four valid cuts and asked which one could be used to find the maximum flow, meaning the minimum cut. Only 36.9% chose correctly. You need both rules from Part 3 to get each capacity right, then the smallest capacity wins.
All four lines separate the source from the sink, so all four are valid cuts. The maximum flow equals the minimum cut, so find each capacity and take the smallest.
Cut
Capacity
$C_1$
$80 + 70 = 150$
$C_2$
$45 + 65 + 40 + 55 = 205$
$C_3$ the 40 pointing back up-left is not counted
$90 + 65 + 55 = 210$
$C_4$
$90 + 65 + 45 = 200$
$C_1$ is smallest at 150, so the maximum flow is 150. 36.9% of students chose (A). 30.7% chose (C) and 17.3% chose (D), the cut next to the sink. A cut that looks like a bottleneck on the page is not always the smallest one. Add them up.
Answer
(A) C1
2020 Paper 1 Question 21
Paper 1 · Simple familiar · [5 marks]
This network shows the maximum number of supplies (in tonnes) that can be transported from a warehouse to a cyclone shelter along each road each day during an emergency.
Note: If you make a mistake in the network, cancel it by ruling a single diagonal line through your work and use the additional network on page 18 of this question and response book.
a) Use the ‘maximum flow, minimum cut’ theorem to determine the maximum amount of supplies that can reach the cyclone shelter each day. [3 marks]
b) During a cyclone, the intersection at vertex A is damaged and no longer allows for any supplies to pass through it. What is the new maximum amount of supplies each day that can reach the cyclone shelter? [2 marks]
a) The middle nodes are A, B and C, so there are $2^3 = 8$ cuts. List them by source side:
Source side
Capacity
W
$50 + 30 + 40 = 120$
W, A
$20 + 30 + 40 = 90$
W, B C→B points back
$50 + 40 + 40 = 130$
W, C
$50 + 30 + 20 + 30 = 130$
W, A, B C→B points back
$20 + 40 + 40 = 100$
W, A, C
$20 + 30 + 20 + 30 = 100$
W, B, C
$50 + 40 + 30 = 120$
W, A, B, C
$20 + 40 + 30 = 90$
1 mark · correctly identifies all the possible cuts
1 mark · correctly calculates the flow across all the cuts
Two cuts tie for smallest at 90. Both contain A→S. Animated: the eight cuts in the order of the table, then the two smallest.
The minimum cut is 90, so the maximum flow is 90 tonnes per day.
1 mark · states maximum flow across minimum cut
The guide numbers seven cuts and leaves out the source side {W, A, C}, and its note says “Accept any 7 or 8 possible valid cuts”. Follow-through is allowed on the last mark.
b) With A out of action, W→A and A→S carry nothing. Set both to 0 and recalculate. The eight cuts become 70, 70, 80, 80, 80, 80, 70 and 70 (in the order of the table), so the minimum is 70.
1 mark · recalculates flow across minimum cut
1 mark · states new maximum flow
Both 90 cuts contained A→S, worth 20, which is why the answer drops by exactly 20 here. Show the recalculated cuts anyway, because the first mark is for the recalculation.
Answer
a) 90 tonnes per day · b) 70 tonnes per day
2023 Paper 1 Question 21
Paper 1 · Simple familiar · [4 marks]
The road network shows the number of vehicles per hour travelling from the airport to the town centre.
a) Determine the capacity of cut X. [1 mark]
b) Determine the maximum flow from the airport to the town centre. [2 marks]
c) During a weather emergency, all roads to and from the bridge are closed to vehicles. Determine the maximum flow from the airport to the town centre during this time. [1 mark]
a) Cut X has the airport and the bridge on the source side. It crosses Airport→College (200), Bridge→Town centre (100), Bridge→Showground (140) and College→Bridge (50). The 50 runs from College, on the far side, back to Bridge, so it is not counted:
1 mark · correctly determines the capacity of cut X
b) Middle nodes College, Bridge and Showground give eight cuts:
Source side (with Airport)
Capacity
nothing else
$200 + 150 = 350$
College
$150 + 50 + 120 = 320$
Bridge (cut X)
$200 + 100 + 140 = 440$
Showground
$200 + 150 + 80 = 430$
College, Bridge
$120 + 100 + 140 = 360$
College, Showground
$150 + 50 + 120 + 80 = 400$
Bridge, Showground
$200 + 100 + 80 = 380$
College, Bridge, Showground
$120 + 100 + 80 = 300$
1 mark · correctly identifies an appropriate method
The minimum cut crosses the three roads into the town centre. Animated: the eight cuts in the order of the table, source side shaded.
The minimum cut crosses the three roads into the town centre, so the maximum flow is
$$120 + 100 + 80 = 300$$
300 vehicles per hour.
1 mark · identifies maximum flow
The guide accepts alternative methods, “e.g. other representations for augmented paths or identifies the minimum cut”, and allows follow-through. Its sample shows a flow on every edge: 170 of 200 to College, 130 of 150 to Bridge, the full 50 from College to Bridge, 80 of 140 from Bridge to Showground, and 120, 100 and 80 filling the three roads into town.
c) With every road to and from the bridge closed, the only route left is Airport → College → Town centre. Its smallest edge limits it:
$$\min(200,\ 120) = 120$$
The maximum flow is 120 vehicles per hour.
1 mark · correctly determines the maximum flow
Taking 440 from a) as the maximum flow, or adding the backward 50 to get 490, are the slips to avoid. A cut someone drew for you is only one cut, and it need not be the minimum.
Answer
a) 440 · b) 300 · c) 120 vehicles per hour
Try it yourself
Move the cut and find the smallest
This is the network from 2020 Paper 1 Question 21. Put each middle vertex on the source side or the sink side. Each choice is one cut, and the lab adds only the edges that cross it forwards. Try all eight, then close vertex A to rerun part b.
Shaded vertices are on the source side. Orange edges cross the cut forwards and count. Blue dashed edges cross backwards and do not.
Which side of the cut is each vertex on?
The warehouse (W) is always on the source side and the cyclone shelter (S) is always on the sink side.
Source side
Capacity
Cuts you have tried ( of 8)
Part 5
When the question changes the network
Three past questions change the network after you have the answer: 2020 Question 21 b) damages a vertex, 2023 Question 21 c) closes roads, and 2025 Paper 2 Question 3 asks which single upgrade reaches a target. None of them can be answered by finding the minimum cut and stopping.
The change
What to do
A node or road is lost
Set its edges to 0, or delete them, and recalculate every cut. The minimum can move to a different cut.
One edge is upgraded
An upgrade only helps if the edge is on the minimum cut. If two cuts tie for minimum, the edge must be on both.
A target flow is given
Raise the edge by the gap between the target and the current maximum, then recheck every cut to make sure none is now below the target.
Building the network from a table
2025 gave the pipes as a table instead of a diagram. Read it like an adjacency matrix: the row is where a pipe starts, the column is where it ends, and a dash means no pipe. Every number becomes one arrow. Count them before you go on, since the first mark was for “all 5 vertices and 6 directed edges and their correct weights”.
2025 Paper 2 Question 3
Paper 2 · [5 marks]
Stormwater flows through a network of pipes from a source (A) to a river (E). The table shows the maximum flow rate (L/sec) through each pipe connecting different parts of the network.
From \ To
B
C
D
E
A
32
38
—
—
B
—
12
—
—
C
—
—
20
24
D
—
—
—
20
An engineer will upgrade only one pipe to change the maximum flow from A to E to 45 L/sec.
Use a flow network diagram to determine the new maximum flow rate for the upgraded pipe.
Note: If you make a mistake, cancel it by ruling a single diagonal line through your work and use the additional response space at the back of this book.
Step 1 · Draw the network. Each number in the table is one pipe, from the row letter to the column letter. That gives 5 vertices and 6 directed edges.
The two minimum cuts, both 44. C→E (orange) is the only pipe on both.
1 mark · correctly constructs flow network diagram showing all 5 vertices and 6 directed edges and their correct weights
Step 2 · Find every cut. The middle nodes are B, C and D, so there are eight.
Source side
Capacity
A
$32 + 38 = 70$
A, B
$38 + 12 = 50$
A, C BC points back
$32 + 20 + 24 = 76$
A, D CD points back
$32 + 38 + 20 = 90$
A, B, C
$20 + 24 = 44$
A, B, D CD points back
$38 + 12 + 20 = 70$
A, C, D BC points back
$32 + 24 + 20 = 76$
A, B, C, D
$24 + 20 = 44$
1 mark · applies an appropriate method for determining maximum flow
The guide’s sample lists four cuts drawn left to right (70, 50, 44 and 44), and its notes name two appropriate methods: “finding all the cuts and calculating flow across those cuts” and “showing flow and capacity on all the edges”. Follow-through is allowed.
Step 3 · The current maximum flow. Two cuts tie for smallest at 44 L/sec: the cut through CD and CE ($20 + 24$) and the cut through CE and DE ($24 + 20$). So the original maximum flow is 44 L/sec.
1 mark · determines original maximum flow from source to river
Step 4 · Which pipe. Raising the flow means raising every minimum cut at once. Only CE lies on both, so CE is the only single pipe that works. Upgrading DE raises one 44 cut and leaves the other at 44, so the flow stays at 44. Upgrading AC, the biggest pipe, changes nothing, because it is on neither.
1 mark · identifies upgraded pipe
Step 5 · How much. The target is 45, one more than 44, so CE goes from 24 to 25. Recheck the cuts: the two that contained CE become 45, and the next smallest is 50, so the maximum flow is now 45 L/sec as required.
New maximum flow rate for the pipe from C to E:
$$24 + 1 = 25\ \text{L/sec}$$
1 mark · determines new maximum flow rate for upgraded pipe
The guide accepts the pipe and its new rate “clearly indicated in table or on diagram”. The subject report’s chosen response also highlighted “a justified decision for which pipe would be upgraded”, so say why CE and not DE.
Answer
Upgrade the pipe from C to E to 25 L/sec
The idea this question tests
•Upgrading the biggest pipe feels sensible and achieves nothing. AC, at 38, is on neither minimum cut.
•When two cuts tie for minimum, the upgrade must be on both. Here only CE qualifies.
•The recheck in Step 5 matters. Raising one cut can leave another as the new minimum, and the flow then rises less than you expected.
Part 6
Where the marks are in a flow question
The marking guides give one mark per step, and most of the steps come before the final number. These are the descriptors from the three questions that asked for a maximum flow.
Question
The response… (and the guide’s notes)
2020 Q21 a)
correctly identifies all the possible cuts · correctly calculates the flow across all the cuts · states maximum flow across minimum cut Accept any 7 or 8 possible valid cuts. Follow-through on the last mark.
2023 Q21 b)
correctly identifies an appropriate method · identifies maximum flow Accept augmented paths or identifying the minimum cut. Follow-through allowed.
2025 P2 Q3
constructs the diagram · applies an appropriate method · determines original maximum flow · identifies upgraded pipe · determines new maximum flow rate Methods include finding all cuts or showing flow and capacity on all edges. The original maximum may be implied by later working.
Listing every cut is the method the subject reports showcase and the safest one, though markers also accept a flow drawn on every edge. If you use the flow method, show the flow and the capacity on every edge, as the 2023 guide does, and check that the flow into each middle node equals the flow out.
Units and wording
Cut capacities are bare numbers in the working. The maximum flow is an amount, so give it in the question’s units: tonnes per day in 2020, vehicles per hour in 2023, L/sec in 2025. Write the link between the two in words, “minimum cut = 44, so maximum flow = 44 L/sec”, which also answers the 2020 report’s point about telling them apart.
Self-checks to run inside the question
Checkpoint
How to run it
Is the cut valid?
Name the source side. The source must be on it and the sink must not.
Direction of each crossed edge
Only edges from the source side to the sink side count.
Did you list every cut?
Three middle nodes means eight cuts. Count your list.
Smallest, not largest
The maximum flow equals the minimum cut. Taking a drawn cut or the largest total are the usual slips.
Is the answer sensible?
The maximum flow can never exceed the total capacity leaving the source, nor the total entering the sink.
Upgrades only help on the cut
An edge that is not on every minimum cut changes nothing.
Recheck after a change
Once a cut rises or falls, a different cut may become the minimum. Check them all again.
Game plan
Your game plan for flow networks
1Find the source and the sink. If the network is given as a table, draw it first: rows are “from”, columns are “to”, one arrow per number.
2If a cut is drawn for you, check it is valid. The source and the sink must be on opposite sides.
3Count the middle nodes and write down every source side. Three middle nodes give eight cuts.
4For each cut, add only the edges leaving the source side. Leave out any edge pointing back.
5Name the smallest total as the minimum cut and write “maximum flow = minimum cut = …” with units.
6If the network changes, recalculate every cut. An upgrade helps only if it is on every minimum cut, so check for ties.
7Sense check: the maximum flow is no more than the total leaving the source or the total entering the sink.
I wrote these four to the QCAA format and checked every answer in Python. Questions 1 to 3 have the Paper 1 shape. Question 4 follows the shape of 2025 Paper 2 Question 3, so attempt it as one question with no parts, and give yourself about 12 minutes.
In a flow network, a cut crosses four edges. Three of them have capacities 14, 9 and 11, directed from the source side to the sink side, and the fourth has capacity 6, directed from the sink side to the source side. The capacity of this cut is
Only edges directed from the source side to the sink side count:
$$14 + 9 + 11 = 34$$
The edge of capacity 6 points back towards the source side and contributes nothing. (A) subtracts it, (C) adds it, and (D) adds it twice.
Answer
(B) 34
Question 2 of 4
Skill 3: Minimum cut and maximum flow · Simple familiar · [4 marks]
Water flows from a source S to a sink T through the following pipes, with capacities in kilolitres per hour: S to P 30, S to Q 25, P to Q 10, P to T 22, Q to T 26.
a) Determine the capacity of the cut that separates T from all other nodes. [1 mark]
b) Determine the maximum flow from S to T, showing the capacity of each cut you consider. [3 marks]
The cut around T is the minimum. Animated: the four cuts in turn.
a) The cut isolating T crosses PT and QT:
$$22 + 26 = 48\ \text{kL/h}$$
1 mark · correctly determines the capacity of the cut
b) Two middle nodes, P and Q, give four cuts:
Source side
Capacity
S
$30 + 25 = 55$
S, P
$25 + 10 + 22 = 57$
S, Q PQ points back
$30 + 26 = 56$
S, P, Q
$22 + 26 = 48$
1 mark · identifies all four cuts
1 mark · correctly calculates the capacity of each cut
The smallest is 48, so the minimum cut is 48 and the maximum flow from S to T is 48 kL/h.
1 mark · states the maximum flow from the minimum cut, with units
The marks are for listing the cuts with their capacities. A response naming only the 48 has asserted the answer without showing it.
A student claims that a line is a valid cut provided it crosses at least one edge leaving the source, and that its capacity is the total of all edges it crosses.
Provide a justified decision about whether the student’s claim is correct. [3 marks]
Crossing one edge leaving the source is not enough. Flow can leave the source along the other edges and reach the sink without crossing the line. A valid cut must intercept every path from source to sink. In 2020 Question 21, a line crossing only Warehouse→A leaves the route Warehouse → B → Cyclone shelter open.
1 mark · explains why crossing one edge leaving the source does not make a valid cut
The capacity is not the total of all edges crossed. Only edges directed from the source side to the sink side count. Edges running back towards the source side are left out.
1 mark · explains that backward edges are not counted in the capacity
Both parts of the claim are wrong, so the claim is incorrect.
1 mark · provides a decision supported by both reasons
Justify, don’t assert. “The claim is incorrect” on its own earns nothing, because the decision mark depends on the reasons before it.
Data flows through a network from a server A to a terminal E, with capacities in gigabits per second: A to B 40, A to C 35, B to D 18, B to E 20, C to D 22, C to E 15, D to E 30.
A technician will upgrade only one link to raise the maximum flow from A to E as far as possible. Determine which link should be upgraded and the greatest maximum flow that can then be achieved, explaining why no further improvement is possible from a single upgrade.
This has the shape of 2025 Paper 2 Question 3: find the bottleneck, work out which single change moves it, then find what becomes the new bottleneck.
The minimum cut (65) surrounds E. The cut around A (75) is what caps any single upgrade.
Source side
Capacity
A
$40 + 35 = 75$
A, B
$35 + 18 + 20 = 73$
A, C
$40 + 22 + 15 = 77$
A, D BD, CD point back
$40 + 35 + 30 = 105$
A, B, C
$18 + 20 + 22 + 15 = 75$
A, B, D CD points back
$35 + 20 + 30 = 85$
A, C, D BD points back
$40 + 15 + 30 = 85$
A, B, C, D
$20 + 15 + 30 = 65$
The eight cuts are 65, 73, 75, 75, 77, 85, 85 and 105, so the current maximum flow is 65 Gb/s.
1 mark · determines the current maximum flow from all the cuts
Only BE, CE and DE are on the minimum cut, so only they can help.
1 mark · identifies the links on the minimum cut
Upgrading CE or DE alone caps at 73, the cut AC + BD + BE, which contains neither of them. Upgrading BE alone gets further, because BE is on the 73 cut too.
1 mark · compares the candidate upgrades using the cuts that limit them
Raise BE from 20 to 30. The 65 cut becomes $30 + 15 + 30 = 75$ and the 73 cut becomes $35 + 18 + 30 = 83$, so the smallest cut is now 75 and the maximum flow is 75 Gb/s.
1 mark · determines the upgrade to BE and the new maximum flow
No further improvement is possible from one upgrade, because the cut leaving the source, AB + AC $= 40 + 35 = 75$, does not contain BE. Raising BE beyond 30 leaves that cut at 75.
1 mark · explains why the cut leaving the source caps the improvement
30 is the smallest upgrade that reaches 75. Any larger value for BE gives the same 75.
Answer
Upgrade B to E from 20 to 30 Gb/s, giving a maximum flow of 75 Gb/s
Sources: QCAA General Mathematics external assessment papers (Paper 1 and Paper 2) and marking guides, 2020 to 2025. General Mathematics 2025 v1.3 general senior syllabus, Unit 4 Topic 5, compared with the 2019 syllabus. QCAA General Mathematics subject reports, 2020 to 2025. General Mathematics formula book. Every cut capacity and maximum flow on this page was checked in Python against the published marking guides.
