Minimum spanning trees and connector problems (QCE General Mathematics Unit 4)

Syllabus dot point

“Understand the meaning of tree, spanning tree and minimum spanning tree, determine a minimum spanning tree in a weighted connected graph, and solve practical problems involving minimum spanning trees, such as minimising the length of cable needed to connect several sites”

14 min readUpdated 23 Sep 2026

Quick answer

A tree is a connected graph with no cycles, and a tree on $v$ vertices has $v - 1$ edges. A spanning tree includes every vertex of a graph, and a minimum spanning tree is the spanning tree with the least total weight: the cheapest way to connect every site. Find it with Prim's algorithm (start anywhere, repeatedly add the smallest edge to a new vertex) or check it with Kruskal's algorithm (add edges from smallest up, skipping any that form a cycle). Multiply by the unit cost for the total cost; the edges left out give the possible savings.

Jump to a section

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

What this dot point is asking

Many practical problems ask for the cheapest way to connect a set of places: laying cable from a power station to several substations, piping water to houses, or deciding which paths in a park to keep so every location is still reachable. These are minimum connector problems, and the answer is a minimum spanning tree.

The QCAA General Mathematics 2025 syllabus (Unit 4, Topic 4, Networks and decision mathematics 1, "Trees and minimum connector problems") asks you to

understand the meaning of tree, spanning tree and minimum spanning tree,
determine a minimum spanning tree in a weighted connected graph, and
solve practical problems involving minimum spanning trees.

The syllabus does not name an algorithm. Prim's algorithm is the standard method and is taught below; Kruskal's algorithm gives the same total and is a good check.

The answer

Trees

A tree is a connected graph with no cycles. Three facts follow:

A tree with $v$ vertices has exactly $v - 1$ edges.
There is exactly one path between any two vertices of a tree.
Removing any edge disconnects it; adding any edge creates a cycle.

So a tree is the "leanest" possible connected graph: every edge is essential.

Spanning trees

A spanning tree of a connected graph is a subgraph that is a tree and includes every vertex of the graph. A graph usually has many spanning trees: each is a way of keeping everything connected while removing edges until no cycles remain. For a graph with $v$ vertices, every spanning tree has $v - 1$ edges.

Minimum spanning trees

In a weighted graph (a network), the minimum spanning tree is the spanning tree with the smallest total weight. It connects every vertex at the least total length, cost or time. A network can have more than one minimum spanning tree when edges have equal weights, but they all have the same total weight.

Prim's algorithm

Prim's algorithm grows one tree, one vertex at a time.

Choose any starting vertex.
Look at every edge that joins a vertex in the tree to a vertex not yet in the tree. Choose the one with the smallest weight (if there is a tie, choose either).
Add that edge and its new vertex to the tree.
Repeat step 2 until every vertex is in the tree ( $v - 1$ edges).

Because each new edge always reaches a new vertex, Prim's algorithm can never create a cycle. For the network above, starting at A:

Step	Tree so far	Candidate edges (to a new vertex)	Chosen
1	A	A-B 7, A-C 5, A-D 9	A-C 5
2	A, C	A-B 7, A-D 9, C-D 8, C-F 12	A-B 7
3	A, B, C	A-D 9, B-D 6, B-E 11, C-D 8, C-F 12	B-D 6
4	A, B, C, D	B-E 11, C-F 12, D-E 4, D-F 7	D-E 4
5	A, B, C, D, E	C-F 12, D-F 7, E-F 10, E-G 5	E-G 5
6	A, B, C, D, E, G	C-F 12, D-F 7, E-F 10, F-G 6	F-G 6

Total weight $5 + 7 + 6 + 4 + 5 + 6 = 33$ , using $7 - 1 = 6$ edges.

Prim's algorithm from a table

Networks are often given as a table of distances. The method is the same: keep a list of the vertices in the tree, and at each step scan only the rows of vertices in the tree for the smallest entry in a column of a vertex not yet in the tree.

	P	Q	R	S	T
P		14	22	18	25
Q	14		12	20	17
R	22	12		15	11
S	18	20	15		19
T	25	17	11	19

Start at P: the smallest entry in row P is P-Q (14). Rows P and Q, columns R, S, T: smallest is Q-R (12). Rows P, Q, R, columns S, T: smallest is R-T (11). Rows P, Q, R, T, column S: smallest is R-S (15). Total $14 + 12 + 11 + 15 = 52$ .

Kruskal's algorithm (a check)

List all edges from smallest to largest. Accept each edge in turn unless it would form a cycle, and stop when you have $v - 1$ edges. For the network above: D-E 4 (accept), A-C 5 (accept), E-G 5 (accept), B-D 6 (accept), F-G 6 (accept), A-B 7 (accept); that is 6 edges, so stop. Same total, 33.

Practical problems

Least cost to connect. Cost $=$ total weight of the minimum spanning tree $\times$ cost per unit.
Savings from removing links. The links not in the minimum spanning tree are the ones that can be removed while keeping everything connected: saving $=$ (total of all edges $-$ minimum spanning tree) $\times$ cost per unit.
A link that must be included. Put it in first, then continue with Prim's or Kruskal's algorithm as usual. The total can only stay the same or increase.
A link that cannot be used. Delete it from the network and find the minimum spanning tree of what is left.

Remember that a minimum spanning tree minimises the total length of the connections. It does not give the shortest route between two particular vertices; that is a shortest path problem.

Key fact

A tree is connected with no cycles and has $v - 1$ edges. A spanning tree includes every vertex; a minimum spanning tree has the least total weight. Prim's algorithm: start anywhere and repeatedly add the smallest edge from the tree to a new vertex until all $v$ vertices are joined. Kruskal's algorithm: add edges from smallest up, skipping any that form a cycle. Cost $=$ total weight $\times$ rate; savings come from the edges left out.

Worked examples: minimum connector problems

1. Is it a tree?

A connected graph has 8 vertices and 9 edges. Can it be a tree? How many edges must be removed to leave a spanning tree?

Count. A tree with 8 vertices has $8 - 1 = 7$ edges.

Answer. No, it has 9 edges, so it contains at least one cycle. Remove $9 - 7 = 2$ edges (breaking cycles, without disconnecting the graph) to leave a spanning tree.

2. Prim's algorithm from a different start

Repeat Prim's algorithm on the network above, starting at G.

Steps. From G: G-E (5). From {E, G}: E-D (4). From {D, E, G}: the smallest edges to new vertices are D-B (6) and G-F (6), a tie; choose D-B. Then G-F (6). Then B-A (7). Then A-C (5).

Answer. The same six edges, total 33. The starting vertex does not change the total, and in this network the minimum spanning tree is unique.

Marker's note: when there is a tie, say so and state which edge you chose. Either choice leads to a minimum spanning tree.

3. A cabling cost

Six mine sites H, J, K, L, M and N can be joined by the cable routes (m) H-J 320, H-K 410, J-K 280, J-L 450, J-M 470, K-L 390, K-M 360, L-M 240, L-N 500, M-N 310. Cable costs $85 per metre. Find the least cost to connect all sites.

Prim's from H: H-J (320); J-K (280); K-M (360) (the other edges to new sites are J-L 450, J-M 470 and K-L 390; H-K now joins two sites already in the tree); M-L (240); M-N (310).
Check: 5 edges for 6 vertices, all sites included, no cycles.
Total: $320 + 280 + 360 + 240 + 310 = 1510$ m.
Cost: $1510 \times 85 = 128\,350$ , so $128 350.

4. Savings from closing roads

The roads in the network above (all twelve edges) total 90 km. The council maintains roads at $3200 per km per year and wants to close as many as possible while keeping every town reachable. Find the annual saving.

Keep: A minimum spanning tree: 33 km.
Close: $90 - 33 = 57$ km (A-D, B-E, C-D, C-F, D-F and E-F).
Saving: $57 \times 3200 = 182\,400$ , so $182 400 a year.

5. An edge that must be included

In the same network, road C-F (12 km) must be kept. Find the least total length of road that includes it.

Include C-F first. Then apply Kruskal's algorithm to the remaining edges: D-E 4 (accept), A-C 5 (accept), E-G 5 (accept), B-D 6 (accept), F-G 6 (accept). Now all seven towns are joined with 6 edges.

Total. $12 + 4 + 5 + 5 + 6 + 6 = 38$ km, which is 5 km more than the unrestricted minimum. C-F replaces A-B (7) in the tree.

Common traps

Creating a cycle: In Kruskal's algorithm, an edge joining two vertices that are already connected must be skipped. In Prim's algorithm, only consider edges to a new vertex.
The wrong number of edges: A spanning tree on $v$ vertices has exactly $v - 1$ edges. Count before you total.
Choosing the smallest edge anywhere in Prim's algorithm: Prim's only looks at edges leaving the current tree.
Answering with the edges kept when the savings were asked for: Savings come from the edges not in the tree.
Confusing the minimum spanning tree with the shortest path: The route between two vertices along the tree is not necessarily the shortest route in the network.
Leaving out units or the context: Finish with a sentence giving the minimum length (with units) and the cost in dollars.

Exam technique

Show the algorithm, not just the answer: list the edges in the order they are chosen (a table like the one above is ideal), note any ties and any rejected edges, and check that you have $v - 1$ edges. On a diagram, highlight the tree edges clearly. For "evaluate" questions (budgets, savings, claims), calculate the relevant figure, compare it with the given value explicitly, and give a conclusion with a comment on reliability (for example a small margin, or measurements that are approximate).

Note

Suppose you need to connect six towns with power cables, and it does not matter if the power goes the long way round, as long as every town is connected. You want to use as little cable as possible. A minimum spanning tree does exactly that. Start at any town, and keep connecting the nearest town you have not reached yet to the towns you already have, until every town is in. You never build a loop, because a loop would mean some cable was not needed.

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.

Practice5 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.

Show worked answer →

The original map is not reproduced here, so this explainer shows the method and the arithmetic with the path lengths it identifies.

Step 1: find a minimum spanning tree (1 mark): Keeping every location connected with the least total path length means keeping a minimum spanning tree: 8 paths for 9 locations.
Step 2: identify the removable paths (1 mark): The paths not in the minimum spanning tree can be removed. Their lengths total $120 + 185 + 170 + 170 = 645$ m.
Step 3: annual saving (1 mark): $645 \times 214 = 138\,030$ , so $138 030 per year.
Step 4: compare (1 mark): $138 030 is more than $138 000.
Step 5: evaluate (1 mark): The belief is reasonable: removing the paths outside the minimum spanning tree saves about $138 030 a year and every location stays accessible. The margin is small ($30), so a small error in a measured length could change the conclusion.

Practice4 marks

All buildings in a school are connected by underground electricity cables, indicated by the network (all measurements 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.

Show worked answer →

The original network is not reproduced here; the steps show the method with the cable lengths it identifies.

Step 1: minimum spanning tree (1 mark): Connecting every building with the least cable means finding a minimum spanning tree (for example with Prim's algorithm from the admin building). It uses the cables Admin-Class 1, Class 1-Class 3, Class 3-Class 4, Class 4-Class 2, Class 2-Tuckshop and Tuckshop-Sports shed.
Step 2: total length (1 mark): $(15 \times 3) + 20 + 25 + 45 = 135$ m.
Step 3: cost (1 mark): $135 \times 1200 = 162\,000$ , so $162 000.
Step 4: evaluate (1 mark): $162 000 exceeds the $155 000 budget by $7000. Because a minimum spanning tree is the cheapest way to connect every building, no plan that connects them all fits the budget.

Original4 marks

A network has vertices A to G and edges (weights in km): A-B 7, A-C 5, A-D 9, B-D 6, B-E 11, C-D 8, C-F 12, D-E 4, D-F 7, E-F 10, E-G 5, F-G 6. (a) Use Prim's algorithm, starting at A, to find a minimum spanning tree, listing the edges in the order they are added. (b) State its total length. (c) How many edges does any spanning tree of this network have, and why?

Show worked answer →

(a) From {A}: A-C (5). From {A, C}: A-B (7) (A-D is 9, C-D is 8, C-F is 12). From {A, B, C}: B-D (6). From {A, B, C, D}: D-E (4). Then E-G (5). Then G-F (6). (2 marks)

(b) $5 + 7 + 6 + 4 + 5 + 6 = 33$ km. (1 mark)

(c) 6 edges: a tree on $v = 7$ vertices has $v - 1 = 6$ edges; any more would form a cycle and any fewer would leave a vertex disconnected. (1 mark)

Original4 marks

A mining company needs to lay cable to connect six sites H, J, K, L, M and N. The possible cable routes (m) are: H-J 320, H-K 410, J-K 280, J-L 450, J-M 470, K-L 390, K-M 360, L-M 240, L-N 500, M-N 310. Cable costs $85 per metre laid. (a) Determine the minimum length of cable needed to connect all six sites. (b) The budget is $125 000. Evaluate whether the project is within budget.

Show worked answer →

(a) Prim's algorithm from H: H-J (320), J-K (280), K-M (360), M-L (240), M-N (310). Check: 5 edges for 6 sites, no cycle. Total $320 + 280 + 360 + 240 + 310 = 1510$ m. (2 marks)

(b) Cost $= 1510 \times 85 = 128\,350$ , so $128 350. (1 mark) This is $3350 over the $125 000 budget. Since 1510 m is the least possible length, no layout connecting all six sites is within budget; the company needs about $3350 more or must leave a site unconnected. (1 mark)

Original3 marks

In the network A to G above (all edges total 90 km of road), a council keeps only the roads needed so every town can still reach every other town, with the least total length to maintain. Maintenance costs $3200 per km per year. (a) Find the annual saving. (b) Road C-F must be kept because it is the only route for heavy vehicles. Find the new minimum total length that includes C-F.

Show worked answer →

(a) The minimum spanning tree is 33 km, so $90 - 33 = 57$ km of road can be closed. Saving $= 57 \times 3200 = 182\,400$ , so $182 400 a year. (2 marks)

(b) Include C-F (12) first, then continue choosing the cheapest edges that do not form a cycle: D-E (4), A-C (5), E-G (5), B-D (6), F-G (6). A-B is no longer needed. Total $12 + 4 + 5 + 5 + 6 + 6 = 38$ km. (1 mark)

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

A connected graph has 9 vertices and 8 edges. (a) Must it be a tree? (b) How many edges would a spanning tree of a connected graph with 12 vertices have?

Show worked solution →

(a) Yes. A connected graph with $v$ vertices and $v - 1$ edges has no cycles, so it is a tree. (1 mark)

(b) $12 - 1 = 11$ edges. (1 mark)

foundation2 marks

Define a spanning tree and a minimum spanning tree.

Show worked solution →

A spanning tree of a connected graph is a subgraph that includes every vertex, is connected and has no cycles. (1 mark)

A minimum spanning tree of a weighted connected graph is a spanning tree with the smallest possible total weight. (1 mark)

core3 marks

Distances (km) between five towns: P-Q 14, P-R 22, P-S 18, P-T 25, Q-R 12, Q-S 20, Q-T 17, R-S 15, R-T 11, S-T 19. Use Prim's algorithm starting at P to find the minimum length of road needed to connect all five towns.

Show worked solution →

From P: P-Q (14). From {P, Q}: Q-R (12). From {P, Q, R}: R-T (11). From {P, Q, R, T}: R-S (15) (the others to S are 18, 20 and 19). (2 marks)

Total $14 + 12 + 11 + 15 = 52$ km. (1 mark)

core2 marks

Use Kruskal's algorithm on the five towns in the previous question to check your answer.

Show worked solution →

In order of length: R-T (11) accept, Q-R (12) accept, P-Q (14) accept, R-S (15) accept. Four edges connect five towns, so stop. (1 mark)

Total 52 km, the same as Prim's algorithm. (1 mark)

core2 marks

A network has edges A-B 3, B-C 3, C-D 4, A-D 4 and A-C 5. Find the weight of a minimum spanning tree and explain whether it is unique.

Show worked solution →

Choose A-B (3) and B-C (3); A-C (5) would form a cycle. Then either C-D (4) or A-D (4) connects D. (1 mark)

Total 10. It is not unique: {A-B, B-C, C-D} and {A-B, B-C, A-D} both have weight 10. (1 mark)

exam3 marks

A student finds a "minimum spanning tree" for a 6-vertex network by always choosing the shortest edge in the whole network that has not yet been used, and ends up with 6 edges totalling 41. Identify the error and how to fix it.

Show worked solution →

A spanning tree on 6 vertices must have exactly 5 edges; 6 edges means a cycle has been included. (1 mark)

The student did not reject edges that join two vertices already connected (Kruskal's algorithm requires this check). (1 mark)

Fix: work through the edges in order of weight, but skip any edge that would form a cycle, and stop once 5 edges have been chosen. The heaviest edge in the cycle should not be in the tree. (1 mark)

Practise this

Sources & how we know this

General Mathematics General senior syllabus 2025 — QCAA