Understand the idea.
Connect all sites without cycles
A spanning tree connects every vertex without a cycle. For vertices it contains exactly edges. A minimum spanning tree has the smallest possible total edge weight among these connected, cycle-free selections.
The objective is total installation cost or another stated edge total. It does not promise the shortest journey between every pair of sites, and a tree supplies no backup route if one of its edges fails.
Prim grows a connected set
Prim’s algorithm grows one connected tree. Begin at any vertex, then choose a cheapest edge crossing from an included vertex to an excluded one. Add its outside endpoint and repeat until all vertices are included.
Reconsider the crossing edges after each addition. An edge between two included vertices cannot add a new site and would create a cycle. Ties can produce different minimum trees; a disconnected network has no spanning tree covering all vertices.
See the method in action.
Grow from A
Apply Prim’s algorithm to the displayed graph, starting at A.
Worked solution
- 1
Start at A and join C.
Among the edges leaving A, weight two is smaller than the A–B weight four.
- 2
Join B to the current tree.
From the included set containing A and C, C–B is the cheapest crossing edge.
- 3
Join D.
The remaining crossing choices have weights five, eight and ten; choose five.
- 4
Join the last vertex E.
With D included, D–E is cheaper than the remaining C–E edge of weight ten.
- 5
Total and check the tree.
Prim’s crossing-edge choices connect all five vertices without a cycle and certify a minimum spanning tree.
Minimum tree A–C, C–B, B–D, D–E; total 10.
A route need not span
Edges are A–B (1), B–C (1), A–C (3). A student selects A–B only. Is this a spanning tree?
Worked solution
- 1
Check whether all vertices are included.
Selecting A–B alone leaves C disconnected, so it does not span the three-vertex network.
- 2
Add the cheapest connection to C.
B–C joins the missing vertex more cheaply than A–C.
- 3
Total and verify minimum cost.
The selection has two edges and no cycle; any spanning tree needs two edges, each of weight at least one.
No; the minimum spanning tree is A–B and B–C, total 2.
Try it yourself.
Check your understanding
How many edges does a tree connecting 7 vertices have?
Show answer & reasoning
6.
A tree on vertices has edges. For seven connected vertices, edges are required.
Keep practising
6 worksheet questions · 12 marks
Read the questions online
- Find a minimum spanning tree for A–B (3), A–C (4), B–C (2).2 marks
- Can all three sides of a triangle form a tree on its three vertices?2 marks
- A connected selection has 5 vertices and 4 edges. What must be checked before calling it a spanning tree of the original network?2 marks
- Prim has reached A and B. Candidates are A–C (7), B–D (5), C–D (1). What is next?2 marks
- A minimum tree costs 120 dollars. Adding a backup link between two existing vertices costs 18 dollars. Give the new cost and explain whether the selection remains a tree.2 marks
- Two spanning trees have the same minimum total 24 but different edges. Must one be wrong?2 marks
Read the worked solutions
Equivalent correct methods earn the corresponding marks. Include units where asked.
- Find a minimum spanning tree for A–B (3), A–C (4), B–C (2).2 marks
The two cheapest edges connect all vertices.
They do not create a cycle.
A–B and B–C, total 5. - Can all three sides of a triangle form a tree on its three vertices?2 marks
They form a cycle.
A three-vertex tree has two edges.
No. - A connected selection has 5 vertices and 4 edges. What must be checked before calling it a spanning tree of the original network?2 marks
Spanning means none is omitted.
Connectedness and edges then establish a tree.
That all original vertices are included. - Prim has reached A and B. Candidates are A–C (7), B–D (5), C–D (1). What is next?2 marks
C–D does not touch the current tree.
B–D is the cheapest valid joining edge.
B–D (5). - A minimum tree costs 120 dollars. Adding a backup link between two existing vertices costs 18 dollars. Give the new cost and explain whether the selection remains a tree.2 marks
.
The extra link creates a cycle and an alternative route.
138 dollars; it is no longer a tree. - Two spanning trees have the same minimum total 24 but different edges. Must one be wrong?2 marks
Tied weights can produce multiple optimum trees.
Check connectedness and the absence of cycles for each.
No.
Curriculum reference & lesson scope
SACE Board of South Australia
Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.
Official curriculum source ↗