QLDGeneral MathematicsSyllabus dot point

Topic 3: Networks and decision mathematics - how do we connect every vertex of a network at the least total cost?

Define a tree and a spanning tree, identify the minimum spanning tree of a weighted connected graph using Prim's algorithm, calculate its total weight, and apply minimum spanning trees to minimum connector problems such as cabling or pipelines

A focused answer to the QCE General Mathematics Unit 4 dot point on minimum spanning trees. Covers trees and spanning trees, Prim's algorithm for finding the minimum spanning tree of a weighted graph, calculating total weight, and applying minimum connector problems to real cabling and pipeline contexts, with arithmetic-verified worked examples for IA3 and the external assessment.

Generated by Claude Opus 4.76 min answerUpdated 2026-05-29

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

What this dot point is asking

QCAA wants you to connect every point in a network using the cheapest possible set of links, with no wasted connections. The structure that does this is the minimum spanning tree, and the algorithm you apply is Prim's algorithm. You define what a tree and a spanning tree are, build the minimum spanning tree from a weighted graph, total its weight, and interpret the result as the least-cost way to cable, pipe or pave between sites. This is a distinct sub-topic of Unit 4 Topic 3 and a reliable IA3 and external-assessment question.

The answer

Trees and spanning trees

A tree is a connected graph with no cycles. A tree on $v$ vertices always has exactly $v - 1$ edges, the smallest number that keeps it connected. A spanning tree of a connected graph is a subgraph that is a tree and includes every vertex of the original graph. A graph can have many spanning trees.

The minimum spanning tree

When the edges carry weights (distances, costs, times), the minimum spanning tree is the spanning tree whose total edge weight is the smallest. It is the cheapest way to connect every vertex with no redundant link. This solves the minimum connector problem.

Prim's algorithm

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

Start at any vertex.
Of all edges that join a vertex already in the tree to a vertex not yet in the tree, choose the one with the smallest weight.
Add that edge and its new vertex to the tree.
Repeat until every vertex is included.

The key discipline is that at each step you only consider edges leaving the current tree, and you never add an edge that would create a cycle (its other end is already in the tree). When all $v$ vertices are connected you will have used exactly $v - 1$ edges.

Total weight and interpretation

Add the weights of the chosen edges to get the total weight of the minimum spanning tree. In a connector problem this total is the minimum cost or length to link every site. Note that the minimum spanning tree gives the cheapest connection, not the shortest route between any two particular vertices; that is a different problem.

Worked example

Building a minimum spanning tree with Prim's algorithm

A network has four towns A, B, C, D with connection costs (in thousands of dollars): A-B $= 4$ , A-C $= 3$ , B-C $= 2$ , B-D $= 5$ , C-D $= 6$ . Find the minimum spanning tree and its total cost.

Step 1: Start at A. Edges leaving A are A-C $= 3$ and A-B $= 4$ . Choose the smaller, A-C $= 3$ . Tree now has A, C.

Step 2: Edges leaving {A, C} to a new vertex: A-B $= 4$ , C-B $= 2$ , C-D $= 6$ . Smallest is C-B $= 2$ . Add it. Tree now has A, C, B.

Step 3: Edges leaving {A, C, B} to the last vertex D: B-D $= 5$ , C-D $= 6$ . Smallest is B-D $= 5$ . Add it. Tree now has all four vertices.

Step 4: Count edges. With four vertices the tree uses $4 - 1 = 3$ edges: A-C, C-B, B-D. No cycle was formed.

Step 5: Total weight.

3 + 2 + 5 = 10.

Verify: $3 + 2 = 5$ and $5 + 5 = 10$ . The minimum spanning tree costs $\$ 10,000$, the least to connect all four towns.

Common traps

Adding an edge that forms a cycle: Both ends of a chosen edge must not already be in the tree (one end must be new). Adding A-B after A and B are both connected creates a cycle and is invalid.
Choosing the globally smallest edge ignoring the tree: Prim's only considers edges leaving the current tree. Grabbing the smallest edge anywhere in the graph is Kruskal's logic and can go wrong if applied loosely.
Stopping before all vertices are included: The tree is complete only when every vertex is connected, using $v - 1$ edges. Stopping early leaves a vertex isolated.
Confusing the minimum spanning tree with the shortest path: The minimum spanning tree minimises total connection cost, not the distance between two chosen vertices. They answer different questions.
Miscounting edges: A spanning tree on $v$ vertices has exactly $v - 1$ edges; having $v$ or more means a cycle slipped in.

Exam-style practice questions

Practice questions written in the style of QCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2022 QCAA5 marksThe 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 →

Step 1 - find the minimum spanning tree (1 mark). To keep all nine locations connected for the least total path length, find the minimum spanning tree using Prim's algorithm, repeatedly adding the shortest edge that reaches a new location without forming a cycle.

Step 2 - identify the removed paths (1 mark). The paths NOT in the minimum spanning tree are the ones that can be removed. Their lengths total 120 + 185 + 170 + 170 = 645 m.

Step 3 - convert to annual savings (1 mark): saving = 645 x 214 = $138 030 per year.

Step 4 - compare (1 mark): $138 030 is greater than$ 138 000.

Step 5 - evaluate (1 mark): the manager's belief is reasonable. Removing the paths not on the minimum spanning tree saves about $138 030 each year, which is more than the claimed$ 138 000, while every key location stays accessible.

The saving comes from the edges left out of the spanning tree, not the tree itself; a spanning tree on nine vertices keeps exactly eight paths and any extras can go.

2021 QCAA4 marksAll 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 →

Step 1 - find the minimum spanning tree (1 mark). Use Prim's algorithm to connect every building with the least total cable: starting from Admin, keep adding the shortest cable to a not-yet-connected building without forming a loop. The minimum spanning tree is Admin - Class 1 - Class 3 - Class 4 - Class 2 - Tuckshop - Sports shed.

Step 2 - total length of the tree (1 mark): (15 x 3) + 20 + 25 + 45 = 135 m.

Step 3 - total cost (1 mark): 135 x 1200 = $162 000.

Step 4 - compare and decide (1 mark): the budget is $155 000, which is less than$ 162 000, so the school cannot afford the project.

The minimum spanning tree gives the cheapest possible way to connect every building; if even that exceeds the budget, no connected replacement is affordable.