What are 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.

§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

How do we connect every site in a network at the least total cost?

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

How to solve a connector problem by finding a minimum spanning tree with Prim's algorithm, confirm it has n minus 1 edges, and interpret its total weight as the least connection cost.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-02

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

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

Jump to a section

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

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.

Prim's algorithm

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

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

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.

Exam-style practice questions

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

WACE 20227 marksSix 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 20244 marksExplain 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.