Decision Maths: Graphs, Trees and Minimum Spanning Trees
In the Decision Maths strand of A-level Further Maths, a network is a graph whose edges carry weights (numbers representing cost, distance or time). A tree is a connected graph containing no cycles; a spanning tree of a network connects every vertex using edges taken from the network, with no cycles; and a minimum spanning tree (MST) is a spanning tree whose edges have the smallest possible total weight. It covers representing a network as a table of edges and weights, and finding an MST using Kruskal's algorithm (add edges in ascending weight order, rejecting any that would form a cycle) or Prim's algorithm (grow a single tree from a starting vertex, always adding the cheapest edge to a new vertex).
Before you start
Make sure you're comfortable with these topics first:
Method
- Represent a network as a list of edges with weights (or as a weight table), since neither algorithm needs a drawing to be applied correctly.
- Recall that a tree is a connected graph with no cycles, a spanning tree of a network uses edges from the network to connect every vertex with no cycles, and a network with n vertices needs exactly n-1 edges in any spanning tree.
- Kruskal's algorithm: list every edge in ascending order of weight; go through the list in order, adding each edge to the tree provided it does not create a cycle with the edges already chosen, and stop once n-1 edges have been added.
- To check whether an edge would create a cycle, track which vertices are already connected to each other (in the same 'component'); an edge creates a cycle exactly when both its endpoints are already in the same component.
- Prim's algorithm: start at a chosen vertex; at each step, find the cheapest edge connecting a vertex already in the tree to a vertex not yet in the tree, and add that edge and vertex to the tree; repeat until every vertex is included.
- Track the running total weight of the tree as edges are added, and state this total as the MST weight once the tree is complete.
- Compare the two algorithms: Kruskal's considers edges globally in weight order and can build several separate tree fragments before they join up (efficient when the network is given as a short edge list); Prim's grows a single connected tree outward from one vertex (efficient when the network is given as a dense weight table).
Worked example
A network has vertices A, B, C, D, E, F and edges with weights: A-B 4, A-C 7, B-C 3, B-D 6, C-D 2, C-E 5, D-E 4, D-F 8, E-F 3. Use Kruskal's algorithm to find the minimum spanning tree and state its total weight.
- List the edges in ascending order of weight: C-D (2), B-C (3), E-F (3), A-B (4), D-E (4), C-E (5), B-D (6), A-C (7), D-F (8).
- Add C-D (2): no cycle, since it is the first edge chosen. Running total = 2. Components so far: {C, D}.
- Add B-C (3): connects B to the {C, D} component, no cycle. Running total = 5. Components: {B, C, D}.
- Add E-F (3): connects a new, separate component {E, F}, no cycle. Running total = 8. Components: {B, C, D} and {E, F}.
- Add A-B (4): connects A to the {B, C, D} component, no cycle. Running total = 12. Components: {A, B, C, D} and {E, F}.
- Add D-E (4): connects the {A, B, C, D} component to the {E, F} component, no cycle. This is the 5th edge, and a spanning tree on 6 vertices needs exactly 5 edges, so the tree is now complete. Running total = 16.
- Final answer: minimum spanning tree = {C-D, B-C, E-F, A-B, D-E}, total weight = 16 (the remaining edges B-D, A-C and D-F are rejected, since the tree is already complete).
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1State the definition of a 'tree' in graph theory.Show answer
Answer: A connected graph containing no cycles.
Q2A network has 9 vertices. How many edges must a spanning tree of this network contain?Show answer
Answer: 8 edges (n-1 = 9-1).
Q3A network has edges (with weights) P-Q 5, P-R 9, Q-R 3, Q-S 7, R-S 4. Use Kruskal's algorithm to find the minimum spanning tree and its weight.Show answer
Answer: MST = {Q-R, R-S, P-Q}, total weight = 12 (add in order Q-R(3), R-S(4), P-Q(5); this connects all 4 vertices with 3 edges).
Q4A network has vertices W, X, Y, Z with edges (weights): W-X 2, W-Y 6, X-Y 3, X-Z 8, Y-Z 5 (there is no direct edge W-Z). Starting from W, use Prim's algorithm to find the minimum spanning tree and its total weight.Show answer
Answer: MST = {W-X, X-Y, Y-Z}, total weight = 10 (2+3+5); from W the cheapest edge is W-X(2), then from {W,X} the cheapest new edge is X-Y(3), then from {W,X,Y} the cheapest new edge is Y-Z(5).
Q5Explain why a graph containing a cycle cannot be a tree.Show answer
Answer: A tree is defined as a connected graph with no cycles, so a graph containing a cycle fails this condition by definition; equivalently, a tree on n vertices has exactly n-1 edges, while a cycle needs at least one more edge than that to connect the same vertices.
Q6State one difference between Kruskal's algorithm and Prim's algorithm.Show answer
Answer: Kruskal's algorithm selects edges in order of increasing weight from the whole network, and can build several separate tree fragments before they join up; Prim's algorithm grows a single tree from one starting vertex, always adding the cheapest edge that connects a new vertex to the tree already built.
Q7Explain why the minimum spanning tree of a network is not necessarily unique.Show answer
Answer: If two or more edges in the network have equal weight, more than one spanning tree can achieve the same minimum total weight (a different choice among the equal-weight edges gives a different tree with the same total), so both are equally valid minimum spanning trees.
Exam-style questions
Written in the style of a A Level Further Maths exam paper, with a full mark scheme.
A network has vertices G, H, I, J, K and edges with weights: G-H 6, G-I 4, G-J 9, H-I 3, H-K 8, I-J 5, I-K 7, J-K 2. Use Kruskal's algorithm to find the minimum spanning tree, showing each edge you add and the running total weight.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 7 available
A network has vertices 1, 2, 3, 4, 5 and edges with weights: 1-2 3, 1-4 7, 2-3 2, 2-4 5, 2-5 6, 3-4 4, 4-5 1. Starting at vertex 1, use Prim's algorithm to find the minimum spanning tree, listing the edges in the order they are added and stating the total weight.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 5 available
A connected network has 12 vertices and 17 edges. (a) State the number of edges in any spanning tree of this network. (b) Kruskal's algorithm is applied to the network and rejects some edges because they would form a cycle. State how many edges are rejected in total, explaining your reasoning.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 4 available
See real A Level Further Maths past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the decision maths: graphs, trees and minimum spanning trees worksheet pack - 10 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on decision maths: graphs, trees and minimum spanning trees, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.