Topic guide 12 · Unit 4 Topic 4 · Networks and decision mathematics 1
Trees and minimum spanning trees
A tree is a connected graph with no cycles. A spanning tree is a tree that reaches every vertex of a network, and a minimum spanning tree is one whose edges add to the smallest possible total. In practice it answers one question: what is the least cable, pipe or path that still connects everything?
Finding the tree is a procedure that works every time. The marks get lost around it: a decision that never compares, a cost that never gets calculated, an edge whose length you have to work backwards to find. This guide works through all eight QCAA questions on trees from 2020 to 2025, in the order you need the skills.
8
tree questions in the 2020 to 2025 papers, at least one every year
23
short-response marks on trees, 2020 to 2025
4 of 5
short-response tree questions that ended in a decision against a stated figure
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 trees
Every paper from 2020 to 2025 had at least one tree question. I count eight: three multiple choice items (2020 Q7, 2021 Q12 and 2022 Q9) and five short-response questions worth 23 marks.
Question
What it asked
2021 Paper 2 Q2 · 4 marks
Minimum cable for a school, costed against a $155 000 budget
2022 Paper 2 Q5 · 5 marks
Theme park paths: can removing paths save at least $138 000 a year?
2023 Paper 2 Q3 · 5 marks
Ski lifts: find the length of cable C from the change it makes to the minimum total
2024 Paper 1 Q23 · 4 marks
Draw the minimum spanning tree for a gas pipeline, then test a 2000 km claim
2025 Paper 1 Q23 · 5 marks
Justify why a subgraph is not a tree, then test a ‘less than 25 m’ claim
Every short-response tree question, 2020 to 2025. Trees share Unit 4 Topic 4 with critical path analysis, and together the two carried 50 short-response marks over the six years.
Look at the last column. Paper 1 asks for the tree and then a simple comparison (2000 km in 2024, 25 m in 2025). Paper 2 builds a second step on top of the tree: a cost against a budget (2021), a saving (2022) or an unknown edge (2023). The tree on its own has never been the final answer to a short-response question.
What the subject reports said
•The 2022 report wanted a minimum spanning tree clearly identified on the network diagram, with the vertex sequence, the sum of the lengths and the total length.
•The 2023 report asked for the tree to be shown with a squiggly line, or for the vertex sequence to be written in the response space. The 2024 and 2025 reports asked for blue or black pen, not highlighter, with a thicker or squiggly line, so the response is clearly visible when the paper is scanned.
•The 2025 report listed identifying a minimum spanning tree among the things students did well, and asked for correct terms such as tree and cycle. On 2025 Q23a it praised responses that linked a feature of the subgraph (it has a cycle) to a feature of a tree (no cycles).
What the syllabus says
Unit 4 Topic 4, sub-topic Trees and minimum connector problems, is 4 hours, tied with two other sub-topics as the shortest in Unit 4. It has three dot points:
•Understand the meaning of tree, spanning tree and minimum spanning tree.
•Determine a minimum spanning tree in a weighted connected graph.
•Solve practical problems involving minimum spanning trees, e.g. minimising the length of cable needed to provide power from a single power station to substations in several towns.
The middle dot point names no method. Any correct way of finding the tree earns the marks, so pick the method you find most reliable under pressure and stay with it.
What changed from the old syllabus
The 2019 syllabus said “identify a minimum spanning tree in a weighted connected graph, e.g. using Prim’s algorithm”. The 2025 syllabus names no algorithm, and it adds the meaning of minimum spanning tree to the definitions you need. Every past question in this guide is still in scope.
What the formula book gives you
Section
Supplied
Graphs and networks
Euler’s formula, $v+f-e=2$
Trees
Nothing. There is no tree entry.
Euler’s formula does apply to trees. A tree has no cycles, so it encloses no regions and has only one face, the outside. Put $f=1$ into $v+f-e=2$ and you get $v+1-e=2$, which rearranges to $e=v-1$. That edge count is the one fact in this topic that works like a formula, and Part 2 shows how to use it.
Part 2
A spanning tree reaches every vertex with no cycles
Each definition builds on the one before, so learn them as a sequence.
Term
Definition, and the test
Tree
A connected graph with no cycles. Test: you can get from any vertex to any other, and there is exactly one way to do it.
Spanning tree
A subgraph that is a tree and includes every vertex of the original graph. Test: every vertex is there, it is still connected, and there are no cycles.
Minimum spanning tree
A spanning tree whose total weight is as small as possible. There may be more than one. Test: as above, and no other spanning tree has a lower total.
Five vertices, so every spanning tree has four edges. This is one of several spanning trees of the graph. The four tree edges go in one at a time. Then each dashed edge flashes blue with the cycle it would close.
A loop (an edge that starts and finishes at the same vertex) closes a cycle by itself, so a tree never has a loop either. For walks, paths, cycles and bridges in general, see the graphs and networks guide.
The edge count that acts as a formula
A tree with $v$ vertices has exactly $v-1$ edges. A spanning tree on eight towns has seven edges, and one on ten ski stations has nine.
Count the edges in your answer every time. Too many means you left a cycle in. Too few means some vertex has been cut off.
The right count does not prove you have a tree. Three vertices joined in a triangle plus a fourth vertex on its own has $3=4-1$ edges, but it has a cycle and it is not connected. So also check that every vertex is joined and that there are no cycles.
Four vertices, so a spanning tree needs exactly $4-1=3$ edges, every vertex joined and no cycles.
(A) has only two edges and R is not joined to anything, so it does not span. (C) and (D) both have four edges, one too many. In (C) the extra edge is the loop at S. In (D) it is PR, which closes the cycle P, Q, R, P.
(B) has three edges, reaches all four vertices and has no cycle.
73.5% of students chose (B). 18.3% chose (D), missing the triangle.
A tree has no cycles, and a loop is a cycle on its own, so (A) and (B) are false.
(C) is false because equal weights can give several minimum spanning trees with the same total. 2020 Q7, in Part 3, has three.
(D) is the edge count $e=v-1$ written the other way round, $v=e+1$.
57.2% of students chose (D). 28.9% chose (C), so the idea that a network has only one minimum spanning tree is worth unlearning now.
Answer
(D)
Part 3
Take the cheapest edge that does not close a cycle
Two methods are in general use. The syllabus requires neither, so choose one and practise it until it is automatic.
Method 1: cheapest edge first
1List every edge from shortest to longest.
2Take the shortest edge you have not yet looked at.
3Add it unless it would close a cycle with edges you already have. If it would, reject it.
4Stop when you have $v-1$ edges.
Method 2: grow from one vertex
1Start at any vertex.
2Of all the edges joining a vertex you have to a vertex you do not have, add the shortest.
3Repeat until every vertex is in.
You may see these called Kruskal’s algorithm and Prim’s algorithm. The names earn no marks.
Which to choose
Method 1 is easier to check afterwards, because your working is a sorted list a marker can follow. Method 2 never makes a cycle, so there is nothing to detect and reject.
On a dense diagram, sorting the edges first pays for itself. On a sparse one, growing outward from a corner is quicker. Either way, write down the edges in the order you took them.
Ties give more than one right answer
When two edges of equal length are both available and both legal, you can take either. The trees you end up with are different, but their totals are the same, and every one of them is a correct answer. 2020 Q7 below has three different minimum spanning trees, all 12 km. The 2021 marking guide said “Accept alternative minimum spanning trees” for exactly this reason.
Draw it so the scanner can see it
When the question gives you the diagram, go over each tree edge in blue or black pen with a thick or squiggly line. Highlighter disappears on the scan. If you make a mistake, rule a single diagonal line through it and use the spare diagram at the back of the book.
2020 Paper 1 Question 7
Paper 1 · Multiple choice · [1 mark]
What is the length of the minimum spanning tree for this network? All distances are in kilometres (km).
Four vertices, so the tree has 3 edges. Cheapest first: SR (3), then PQ (4). Now P and Q are joined to each other but not to S and R. All three remaining edges are 5, and any one of them (PS, QS or QR) finishes the tree.
$$3+4+5=12\ \text{km}$$
The edges go in cheapest first: SR, PQ, then QS. One of the three minimum spanning trees. Swap QS for PS or QR and the total is still 12 km.
(A) adds every edge. (D) is the shortest edge alone. (B) matches $4+5+5$, three edges that skip the 3 km edge. The 2020 report published no option percentages.
Answer
(C) 12 km
2024 Paper 1 Question 23
Paper 1 · Simple familiar · [4 marks]
A pipeline network transports natural gas between eight towns (P–W). The length (km) of each pipeline is shown.
a) On the diagram, draw the minimum spanning tree for the pipeline network. [2 marks]
Note: If you make a mistake in the diagram, cancel it by ruling a single diagonal line through your work and use the additional response space at the back of this question and response book.
b) Use your response to Question 23a) to evaluate the reasonableness of 2000 km of pipeline being sufficient to transport natural gas to the eight towns. [2 marks]
a) Eight towns, so the tree needs 7 pipelines. Sort them and work down the list.
Pipeline
Length (km)
Decision
PS
200
Add
ST
210
Add
PQ
230
Add
QR
235
Add
TW
260
Add
TV
280
Add
VW
300
Reject, cycle T, V, W
UW
320
Add, 7th. Stop.
RU 330, QT 345, TU 360 and PV 440 are never needed. Each would close a cycle.
The minimum spanning tree, drawn over the network. The pipelines go in shortest first, and VW flashes blue because it would close the cycle T, V, W. This tree is the only one with the minimum total.
1 mark · correctly draws a spanning tree on the diagram
1 mark · correctly draws the minimum spanning tree on the diagram
b) Add the seven pipelines you drew, then compare with 2000 km.
1 mark · determines minimum total pipeline length (the guide allows follow-through from an error in part a)
$1735 \lt 2000$, so 2000 km of pipeline is sufficient. The claim is reasonable.
1 mark · provides appropriate statement of reasonableness linked to prior working (this mark may only be awarded if the minimum total pipeline length is calculated)
The 2024 report described effective responses as drawing the tree on the diagram, finding the minimum length and giving a statement of reasonableness that links back to that length using comparative words or symbols. “$1735 \lt 2000$, so” does both in one line.
Answer
a) PS, ST, PQ, QR, TW, TV, UW · b) 1735 km < 2000 km, so 2000 km is sufficient
Try it yourself
Build a spanning tree, then make it the minimum
This is the 2024 pipeline network. Tap pipelines on the diagram or in the list to add or remove them. The counters check the two facts a spanning tree needs: 7 pipelines for 8 towns, and no cycles. When you have a tree, the panel compares its total with the minimum.
in your treepart of a cyclenot used
Pipelines
Total length
Groups
Part 4
Justify with the definition, judge with a comparison
Paper 1 has started asking you to explain, not just find. 2025 Q23a gave two marks for saying why a subgraph is not a tree. The pattern is the same one that runs through all of networks: state the condition, show the evidence in this graph, and connect them.
What a justification looks like
Asserting: “This subgraph is not a tree.”
Justifying: “A tree is a connected graph with no cycles. The edges 4.2 m, 5.8 m and 4 m join P to Q to U and back to P, so the subgraph is itself a cycle and it is not a tree. It also has 3 edges on 3 vertices, whereas a tree on 3 vertices has exactly 2.”
The second answer names the defining property, points to the evidence in this diagram and adds the edge count as an independent check. Justify, don’t assert.
The other Paper 1 habit is the claim. Someone says the job can be done with less than some amount. Your answer has three parts: the minimum total, an explicit comparison with the claimed figure, and a verdict in the words of the question. “The claim is reasonable” earns nothing until a number has been compared.
2025 Paper 1 Question 23
Paper 1 · Simple familiar · [5 marks]
The diagram represents a network of six electrical outlets (P–U) and possible locations for connecting cables. Cable lengths are in metres.
a) Justify why a subgraph of the network that contains outlets P, Q and U and connecting cables with lengths 4 m, 4.2 m and 5.8 m is not a tree. [2 marks]
b) An electrician claims that all outlets can be connected using less than 25 m of cables. Identify a minimum spanning tree to evaluate the reasonableness of the claim. [3 marks]
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.
1 mark · determines length of minimum spanning tree (follow-through allowed)
$23.7 \lt 25$, so the claim is reasonable.
1 mark · provides decision (this mark can only be awarded if prior working supports the decision)
Answer
a) The cables form a cycle, and a tree has no cycles · b) 23.7 m < 25 m, so the claim is reasonable
Try it yourself
Step through both methods on the outlet network
The 2025 outlet network again. Pick a method and press Next step. Each row is a line of working you could write in a Paper 2 response: the edge, its length, the decision and the running total. Try growing from different outlets and check that every start gives the same 23.7 m.
tree so farrejected, closes a cycle
not reached yet
Start at
#CablemDecisionTotal
Part 5
In Paper 2 the tree is only the first step
All three Paper 2 tree questions from 2020 to 2025 fall into one of three shapes. Recognising the shape tells you what your last line has to say.
Shape
What the stem says, and what you do after the tree
Cost against a budget (2021 Q2)
A cost per metre and a budget. “Evaluate whether they can afford this project.” After the tree: Multiply the tree total by the rate, compare with the budget, then decide.
Saving (2022 Q5)
A cost per metre per year and a claimed saving. “still allowing visitors to access every key location” After the tree: Find the total of every path and the tree total. The saving is the cost of the difference.
Unknown edge (2023 Q3)
One edge has no length, and the stem says how the minimum total changes when it is added. After the tree: Find the tree without it, apply the change, and work back to the missing length.
“Still allowing visitors to access every key location” and “connect all buildings” are the stem telling you that a spanning tree is required, even though the question never uses the word.
The comparison sentence
The money shapes end the same way: a calculated figure, an explicit comparison with the figure in the stem, then a verdict in context. For the theme park: “The annual saving is $138 030, which is more than the $138 000 the manager claims, so the manager’s belief is reasonable.” Producing $138 030 and stopping leaves the decision mark behind. Calculate, compare, conclude.
Paper 2 is 90 minutes for 38 marks, so a 5-mark question deserves about 12 minutes. That is time to draw the tree properly and write full sentences.
2021 Paper 2 Question 2
Paper 2 · [4 marks]
All buildings in a school are connected by underground electricity cables, indicated by the network. All measurements are in metres.
The electricity cables need replacing and will cost $1200 per metre. The school wants to minimise costs by replacing the shortest length of cable necessary to connect all buildings.
If the school has a budget of $155 000, evaluate whether they can afford this project.
“The shortest length of cable necessary to connect all buildings” is a minimum spanning tree. Seven buildings, so 6 cables.
Four cables are 15 m, and they form a square around Class 1, Class 2, Class 4 and Class 3. Take any three of them, because the fourth would close the square. Then one 20 m cable to the Tuckshop, a 25 m cable to Admin and the 45 m cable from the Tuckshop to the Sports shed.
The tree in the marking guide: Admin, Class 1, Class 3, Class 4, Class 2, Tuckshop, Sports shed. The ties at 15, 20 and 25 m give other trees with the same total.
1 mark · correctly identifies a minimum spanning tree (alternative trees accepted, and a tree drawn on the diagram is accepted)
The cheapest job costs $162 000. Since $155 000 is less than $162 000, the school cannot afford the project.
1 mark · determines if the school can afford the project (follow-through allowed for length, cost and affordability)
Answer
$162 000 > $155 000, so the school cannot afford it
2022 Paper 2 Question 5
Paper 2 · [5 marks]
The map details the length (in metres) of paths between nine key locations in a theme park. The annual cost to maintain the paths is $214 per metre. The theme park manager believes at least $138 000 can be saved each year if some paths are removed, while still allowing visitors to access every key location using paths.
Evaluate the reasonableness of the manager’s belief.
Keeping every location reachable with the least path is a minimum spanning tree. Nine locations, so keep 8 paths. Cheapest first:
Path, length (m)
Decision
Ferris wheel to Toilet, 50
Add
Car park to Bumper cars, 60
Add
Eating area to Bumper cars, 65
Add
Water slide to Laser show, 65
Add
Roller-coaster to Ferris wheel, 70
Add
Toilet to Eating area, 95
Add
Stunt show to Toilet, 110
Add
Roller-coaster to Stunt show, 120
Reject, cycle
Laser show to Bumper cars, 165
Add, 8th. Stop.
The paths to keep. The four removed paths are 120, 185 and the two 170s.
1 mark · correctly identifies minimum spanning tree (alternative approaches accepted, e.g. trial and error to find the total length of removed paths)
1 mark · calculates annual savings (follow-through allowed for the saving and the evaluation)
The saving is $138 030 a year, which is more than $138 000. The manager’s belief is reasonable, as long as the four unnecessary paths are removed and the other eight kept.
1 mark · compares values to evaluate the reasonableness of the belief
1 mark · shows logical organisation communicating key steps (appropriate vocabulary, symbols and conventions, e.g. connecting statements, use of equality signs)
The margin is $30. Round a length or the rate along the way and you can land on the wrong side of $138 000. Every length here is a whole number, so keep them exact.
Answer
Saving $138 030 ≥ $138 000, so the belief is reasonable
2023 Paper 2 Question 3
Paper 2 · [5 marks]
The diagram represents a network of 10 ski stations connected by chairlift cables. The length (km) of each cable is shown, except for cable C, which is closed for maintenance. When cable C reopens, the minimum total cable length required to connect all stations will decrease by 1 km.
Determine the length of cable C and the minimum total cable length required to connect all stations when cable C reopens.
Note: If you make a mistake in the diagram, cancel it by ruling a single diagonal line through your work and use the additional response space at the back of this question and response book.
Ten stations, so the tree has 9 cables. Start without cable C, because it has no length. Cheapest first: 0.8, 1, 1.2, 1.3, 1.4 and 1.8 all go in. Reject 2 (it closes the top loop). Add 2.4 and 2.5. Reject 3 and 3.2. Add 3.6, the cheaper of the two cables joining the top group to the rest, and stop.
The minimum spanning tree without cable C. The cables go in cheapest first, and 2, 3 and 3.2 flash blue because each would close a cycle.
1 mark · correctly identifies minimum spanning tree without cable C
1 mark · shows logical organisation communicating key steps
With cable C open, the tree swaps 3.6 km for 2.6 km and the total drops from 16 km to 15 km. Watch C go in and the 3.6 km cable come out.
The guide’s second method is quicker. Cable C can only shorten the tree by replacing the 3.6 km cable, so C is 1 km shorter than it: $3.6-1=2.6$ km. That method swaps the “total with C” mark for “correctly identifies the 3.6 km cable is not required when cable C reopens”, then finds the new total, $0.8+1.3+1.2+2.6+1+2.5+1.8+1.4+2.4=15$ km.
A cable C of 3.6 km or more would change nothing, which is why the 1 km drop pins it to exactly 2.6 km.
Answer
Cable C is 2.6 km, and the minimum total is 15 km
Part 6
Where the marks are in a tree question
Across the five short-response questions, the marking guides reward the same four things, usually one mark each.
Mark
What earns it, and what the guides allow
The tree
The correct edges, drawn on the diagram or listed. “Accept alternative minimum spanning trees” (2021). “May be implied by subsequent working” (2025). In 2024 a spanning tree that is not minimal could still earn 1 of the 2 marks.
The total
The sum of the tree’s edges, with the unit. Follow-through from an error in the tree (2021, 2023, 2024, 2025).
The conversion
Cost, saving or missing edge. Follow-through again. In 2021 the cost of each arc was accepted in place of the total length.
The decision
An explicit comparison, then a verdict in context. 2024: “may only be awarded if minimum total pipeline length is calculated”. 2025: “can only be awarded if prior working supports decision”.
Two consequences. First, a wrong tree is not the end: a correctly added total and a correctly worded decision can still earn most of the marks. Second, a decision with no number behind it earns nothing, even if it happens to be right.
Paper 2 marks your setting out
The 2022 and 2023 Paper 2 tree questions each gave one mark for “shows logical organisation communicating key steps”: appropriate vocabulary, symbols and conventions, such as connecting statements and equality signs. Label each line (“Removed =”, “Saving =”, “Total with C =”) and write a sentence at the end.
Self-checks to run inside the question
Checkpoint
How to run it
Count the edges
A spanning tree on $v$ vertices has exactly $v-1$ edges. Too many means a cycle remains, too few means a vertex is stranded.
Every vertex included
Spanning means every vertex, including the awkward one in the corner joined by a single long edge.
No cycles
Trace around your tree. If you can get back to a vertex without retracing an edge, a cycle is still there.
Cheapest available
At each step, check that no shorter legal edge was skipped by accident.
Total, then convert
Most Paper 2 questions want a cost or a saving, not a length. Multiply by the rate before you compare.
Kept or removed?
A saving comes from the removed edges. Reporting the tree total alone answers a different question.
Verdict in context
Finish with an explicit comparison against the figure in the stem, then the judgement in the question’s words.
If I had to guess where you’ll lose marks in 2026, it is the last line: a correct total followed by no comparison, or a comparison with the wrong figure.
Game plan
Your game plan for minimum spanning trees
1Read the stem for the trigger. “Connect all”, “access every location” or “shortest length necessary” means a minimum spanning tree.
2Count the vertices and write down how many edges the tree needs, $v-1$.
3Find the tree: cheapest edge first, rejecting any edge that closes a cycle. Write each edge as you take it.
4Draw the tree on the diagram in blue or black pen with a thick or squiggly line, and check the edge count.
5Add the lengths with the unit. If an edge is unknown, find the tree without it and work back from the change the stem gives you.
6Convert if the question asks for money: tree total times the rate, or removed length times the rate for a saving.
7Compare with the figure in the stem using words or a symbol, then give the verdict in context.
I wrote these four to the QCAA format and checked every answer in Python. Question 4 has the complex unfamiliar shape, so attempt it as one question with no parts, and give yourself about 12 minutes.
Question 1 of 4
Skill 1: Trees and the edge count · Simple familiar · [1 mark]
A minimum spanning tree is found for a connected weighted graph with 11 vertices and 18 edges. The number of edges in the minimum spanning tree is
A spanning tree on $v$ vertices has exactly $v-1$ edges:
$$11-1=10$$
The 18 edges in the original graph do not matter. (C) is the number of vertices. (D) is one fewer than the number of edges. (A) is $18-11$.
Answer
(B) 10
Question 2 of 4
Skill 2: Find a minimum spanning tree · Simple familiar · [4 marks]
Seven weather stations A to G are to be joined by fibre cable. The possible connections, in kilometres, are AB 8, AC 5, BC 4, BD 9, CD 7, CE 6, DE 3, DF 11, EF 10, EG 12 and FG 6.
a) Determine the minimum spanning tree and state its total length. [3 marks]
b) State how many cables are required, and justify your answer using a property of trees. [1 mark]
a) Sort the connections and work down the list.
Cable
Length (km)
Decision
DE
3
Add
BC
4
Add
AC
5
Add
CE
6
Add
FG
6
Add
CD
7
Reject, cycle C, D, E
AB
8
Reject, cycle A, B, C
BD
9
Reject, cycle B, C, E, D
EF
10
Add, 6th. Stop.
1 mark · shows the order in which edges were selected, or the cycles rejected
1 mark · correctly identifies the minimum spanning tree: DE, BC, AC, CE, FG, EF
1 mark · correctly determines the total length, with the unit
There is a tie at 6 km, but CE and FG are both needed, so this tree is the only one with the minimum total.
b) A spanning tree on 7 vertices has exactly $7-1=6$ edges, so 6 cables are required.
1 mark · states 6 cables with the reason that a tree on $v$ vertices has $v-1$ edges
Answer
a) DE, BC, AC, CE, FG, EF, total 34 km · b) 6 cables
Question 3 of 4
Skill 3: Justify with the definitions · Simple familiar · [4 marks]
A subgraph of a network has 8 vertices and 8 edges, and every vertex can be reached from every other.
a) Provide a justified decision about whether this subgraph is a tree. [2 marks]
b) Determine how many edges would need to be removed for the subgraph to become a tree, and explain what property those edges must have. [2 marks]
a) A tree on 8 vertices must have exactly $8-1=7$ edges.
1 mark · states that a tree on 8 vertices has 7 edges
This subgraph has 8 edges, so it contains a cycle. It is connected, but it is not a tree.
1 mark · decides it is not a tree because the extra edge means it contains a cycle
b) One edge must be removed, taking the count from 8 to 7.
1 mark · determines that one edge must be removed
That edge must lie on the cycle. Removing an edge that is not on the cycle (a bridge) would disconnect the graph, so it would no longer reach every vertex.
1 mark · explains that the removed edge must lie on the cycle
Answer
a) Not a tree: 8 edges on 8 vertices means a cycle · b) Remove 1 edge, one that lies on the cycle
Question 4 of 4
Skill 4: Cost a minimum spanning tree · Complex unfamiliar · [5 marks]
A regional water authority maintains pipes joining six pumping stations, H to M. The pipe lengths in kilometres are HI 12, HJ 15, IJ 9, IK 14, JK 7, JL 18, KL 11, KM 16, LM 8 and HM 20. Maintenance costs $4300 per kilometre each year, and every station must remain reachable through the pipe network.
The authority’s budget for pipe maintenance next year is $250 000. Farid claims the authority can stay within budget and still afford to keep one additional pipe beyond the minimum required.
Evaluate the reasonableness of Farid’s claim.
“Every station must remain reachable” means a minimum spanning tree. Six stations, so 5 pipes. Cheapest first: JK 7, LM 8, IJ 9, KL 11, HI 12.
1 mark · correctly identifies the minimum spanning tree
1 mark · determines the minimum length and its annual cost
That is within budget, but it only tests half of the claim. The cheapest way to keep one extra pipe is to add back the shortest pipe the tree rejected, IK at 14 km.
1 mark · identifies the cheapest additional pipe as the shortest rejected edge
1 mark · determines the annual cost with the additional pipe
$262 300 is more than the $250 000 budget, by $12 300. The authority can afford the minimum network but not one additional pipe, so Farid’s claim is not reasonable.
1 mark · compares the cost with the budget and gives a decision in context
Stopping at $202 100 checks only the first half of the claim. And the extra pipe has to be the cheapest one available: if even IK breaks the budget, every other choice does too.
Answer
$262 300 > $250 000, so the claim is not reasonable
Sources: QCAA General Mathematics question and response books, multiple choice books and marking guides, 2020 to 2025. General Mathematics 2025 v1.3 general senior syllabus, Unit 4 Topic 4, and the 2019 syllabus for the change note. QCAA General Mathematics subject reports, 2020 to 2025. General Mathematics formula book 2025. Every numerical answer was checked in Python against the published marking guides.
