Minimum spanning trees and connector problems in WACE Mathematics Applications Unit 4

Syllabus dot point

“Solve connector problems by finding a minimum spanning tree using Prim's algorithm and interpret its total weight.”

WACEMathematics ApplicationsUnit 48 min readUpdated 2 Jun 2026

Quick answer

A connector problem asks for the cheapest way to link every site so all are connected, directly or indirectly. The answer is a minimum spanning tree: a set of edges connecting all $n$ vertices with no cycles, using exactly $n - 1$ edges, of least total weight. Prim's algorithm builds it by repeatedly adding the cheapest edge that reaches a vertex not yet in the tree. Its total weight is the least connection cost.

Jump to a section

What this dot point is asking
Connector problems
Prim's algorithm
Kruskal's algorithm as an alternative
Interpreting the result
Exam-style questions

What this dot point is asking

You must solve connector problems with Prim's algorithm, confirm the tree has $n - 1$ edges, and interpret the total weight.

Connector problems

A connector problem asks for the least-cost set of links that connects every vertex. The solution is a spanning tree: it spans (reaches) every vertex, and it is a tree (connected, no cycles). The minimum spanning tree has the smallest possible total weight.

Spanning tree

A spanning tree of a connected graph with $n$ vertices is a subgraph that connects all $n$ vertices using exactly $n - 1$ edges and contains no cycles. The minimum spanning tree is the spanning tree of least total weight.

Prim's algorithm

Prim's algorithm grows the tree outward from a starting vertex.

Prim's algorithm

Start at any vertex; it forms the initial tree.
From all edges joining a tree vertex to a vertex not yet in the tree, choose the one of least weight (break ties arbitrarily) and add that edge and vertex.
Repeat until all $n$ vertices are included; the tree then has $n - 1$ edges.

The key restriction is that each added edge must reach a new vertex; an edge joining two vertices already in the tree would form a cycle and is never added. (Kruskal's algorithm, which adds the globally cheapest cycle-free edge regardless of connection, gives the same minimum spanning tree.)

Always n minus 1 edges, no cycles

A minimum spanning tree of $n$ vertices has exactly $n - 1$ edges and never contains a cycle. If your tree has a loop or the wrong number of edges, you have made an error.

Worked example

Building a minimum spanning tree with Prim's

Five sensors must be networked. Link costs are $AB = 4$ , $AC = 6$ , $BC = 3$ , $BD = 8$ , $CD = 5$ , $CE = 7$ , $DE = 4$ . Start at $A$ .

Step 1: Start the tree at vertex A.

Prim's algorithm begins by placing the starting vertex alone in the tree. The tree is $\{A\}$ . The only edges available are those leaving $A$ : $AB = 4$ and $AC = 6$ . We pick the cheapest, $AB = 4$ , because Prim's always adds the least-weight edge that reaches a vertex not yet in the tree. Add $B$ .

Step 2: Extend to vertex C using the cheapest available edge.

The tree is now $\{A, B\}$ . We list all edges from tree vertices to non-tree vertices: $AC = 6$ , $BC = 3$ , $BD = 8$ . We consider edges from both $A$ and $B$ , because any tree vertex can extend the tree. The cheapest is $BC = 3$ , so we add edge $BC$ and vertex $C$ .

Step 3: Extend to vertex D.

The tree is $\{A, B, C\}$ . Edges to non-tree vertices are $BD = 8$ , $CD = 5$ , $CE = 7$ . The cheapest available edge is $CD = 5$ , so we add edge $CD$ and vertex $D$ .

Step 4: Extend to vertex E to complete the tree.

The tree is $\{A, B, C, D\}$ . The remaining non-tree vertex is $E$ . Edges that reach $E$ are $CE = 7$ and $DE = 4$ . We choose $DE = 4$ as it is cheaper, add edge $DE$ , and include $E$ in the tree. All five vertices are now connected.

Step 5: Record the tree and compute its total weight.

The spanning tree uses edges $AB(4)$ , $BC(3)$ , $CD(5)$ , $DE(4)$ . This is $4$ edges for $5$ vertices, satisfying the $n - 1 = 4$ condition and confirming no cycle exists. The total weight is $4 + 3 + 5 + 4 = 16$ . The cheapest network connecting all five sensors costs $16$ .

Kruskal's algorithm as an alternative

Kruskal's algorithm builds the same minimum spanning tree but works globally rather than growing from one vertex. List all edges in order of increasing weight, then add the cheapest edge that does not form a cycle, regardless of where it is in the network, until $n - 1$ edges have been added. It is often quicker to apply on paper because you sort the edges once and work down the list, skipping any edge that would close a loop. Either algorithm gives the same minimum total weight; choose whichever is faster for the given network.

Interpreting the result

The total weight of the minimum spanning tree is the minimum total cost (length, dollars, cable) to connect every site. It is not the shortest route between two points; a connector problem is about linking everything, not travelling between two named vertices. Read the wording carefully: "connect all", "link every", "least cabling" signal a spanning tree.

In context, the tree's edges are the links that should actually be built, and its total weight is the figure you report (for example, "the cheapest network connecting all six towns uses these five roads and costs $\$30\,000$ "). If a question asks whether a particular link is in the minimum spanning tree, run the algorithm and check; a link can be the cheapest single edge yet still be excluded if adding it would create a cycle with cheaper alternatives.

Common errors

Confusing the spanning tree with a shortest path: A spanning tree connects all vertices; a shortest path links two named vertices.
Adding an edge that forms a cycle: Each edge in Prim's must reach a vertex not yet in the tree.
Wrong number of edges: A minimum spanning tree of $n$ vertices has exactly $n - 1$ edges; more means a cycle, fewer means it is not connected.
Choosing the cheapest overall edge regardless of reach (in Prim's): Prim's only considers edges that extend the current tree to a new vertex.

Exam-style questions

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

WACE 2022-style7 marks

Six towns are to be joined by fibre cable. The possible links (cost in

\$

thousands) are

AB=7

AC=5

BC=8

BD=9

CD=7

CE=5

DE=15

DF=6

EF=8

. (a) Use Prim's algorithm starting at

A

to find the minimum spanning tree. (b) State its total cost and the number of edges.

Show worked answer →

Prim's adds the cheapest edge that reaches a new vertex.

Start at $A$ . Cheapest from $A$ : $AC = 5$ , add $C$ . Cheapest from $\{A,C\}$ : $CE = 5$ , add $E$ . Cheapest reaching a new vertex from $\{A,C,E\}$ : $AB = 7$ (or $CD = 7$ ); take $AB = 7$ , add $B$ . Cheapest reaching new: $CD = 7$ , add $D$ . Cheapest reaching $F$ : $DF = 6$ , add $F$ . (5 marks)

Edges: $AC$ , $CE$ , $AB$ , $CD$ , $DF$ , that is $5$ edges for $6$ towns ( $n-1 = 5$ ). Total cost $= 5 + 5 + 7 + 7 + 6 = 30$ , that is $\$30\,000$ . (2 marks)

Markers reward growing from $A$ by cheapest new-vertex edges, exactly $5$ edges, and total $\$30\,000$ .

WACE 2024-style4 marks

Explain the difference between a minimum spanning tree and a shortest path, and state how many edges a minimum spanning tree of

n

vertices contains.

Show worked answer →

One connects everything; the other links two points.

A minimum spanning tree connects all vertices together at the least total weight with no cycles; it is about the whole network. A shortest path is the route of least total weight between two specific vertices only. (2 marks)

A minimum spanning tree of $n$ vertices has exactly $n - 1$ edges. (2 marks)

Markers reward the connect-everything versus single-journey distinction and the $n - 1$ edge count.

Minimum spanning trees and connector problems in WACE Mathematics Applications Unit 4

What this dot point is asking

Connector problems

Prim's algorithm

Building a minimum spanning tree with Prim's

Step 1: Start the tree at vertex A.

Step 2: Extend to vertex C using the cheapest available edge.

Step 3: Extend to vertex D.

Step 4: Extend to vertex E to complete the tree.

Step 5: Record the tree and compute its total weight.

Kruskal's algorithm as an alternative

Interpreting the result

Exam-style questions

Practise this

Sources & how we know this