Skip to the worksheet
Revision Library
Choose a subject

Decision Maths: Graphs, Trees and Minimum Spanning Trees - Worksheets, Questions and Revision

24 original exam-style questions - 8 pages of questions with a full mark scheme - free printable PDF.

This topic is chapter 2 of A Level Further Maths Decision Topic Workbook and chapter 17 of A Level Further Maths 10-Minute Tests 1.

Revision Library
revisionlibrary.co.uk
A-Level · EDEXCEL

4.2 Decision Maths: Graphs, Trees and Minimum Spanning Trees

Calculator allowed · about 230 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
This question concerns the sum of the degrees of the vertices of a tree.
(a)State the number of edges in a tree with n vertices.(1)
(b)Hence show that the sum of the degrees of the vertices of a tree with n vertices is 2(n - 1).(2)
(c)A tree has 15 vertices. Find the sum of the degrees of its vertices.(2)
(Total for Question 1 is 5 marks)
2
This question concerns the relationship between the degrees of the vertices of a graph and its number of edges.
(a)State the handshaking lemma, relating the sum of the degrees of the vertices of a graph to its number of edges.(1)
(b)A graph has 8 vertices and 11 edges. Find the sum of the degrees of its vertices.(2)
(c)A graph has degree sequence 4, 3, 3, 2, 2, 1, 1. Find the number of edges in the graph.(2)
(d)Explain why the number of vertices of odd degree in any graph must be even.(1)
(Total for Question 2 is 6 marks)
3
The table below represents a network of possible cable routes, with distances in km, between four substations K, L, M, N (a dash indicates no direct route).
KLMN
K-6-9
L6-57
M-5-4
N974-
(a)Use Kruskal's algorithm to find a minimum spanning tree for the network represented by the matrix above, showing the edges in the order considered.(4)
(b)State the two edges of the network that were not required in the minimum spanning tree, and explain why neither could reduce the total weight if used instead of an edge already chosen.(2)
(Total for Question 3 is 6 marks)
4
This question concerns the number of edges in a spanning tree.
(a)State the number of edges in a spanning tree of a connected graph with n vertices, in terms of n.(1)
(b)Hence write down the number of edges in a spanning tree of a connected graph with 9 vertices.(1)
(c)A connected graph has a spanning tree with 12 edges. State the number of vertices in the graph.(1)
(d)A connected network has 10 vertices and 15 edges. State how many edges must be removed to reduce the network to a spanning tree.(2)
(Total for Question 4 is 5 marks)
5
A network has vertices A, B, C, D and edges AB=3, AC=3, BC=5, BD=4, CD=4 (weights in km).
(a)Apply Kruskal's algorithm to find the total weight of a minimum spanning tree for this network.(3)
(b)State two different edge sets that both give a minimum spanning tree of total weight 10, and explain why both are valid minimum spanning trees.(2)
(c)State whether Prim's algorithm, started at vertex A, could also produce either of the two trees found in part (b). Give a reason.(1)
(Total for Question 5 is 6 marks)
6
Five villages, Ashcombe (A), Bramwell (B), Corbridge (C), Dunley (D) and Elsworth (E), are to be connected by underground fibre-optic cable. The possible direct routes and their lengths are: AB=3.2 km, AC=5.6 km, BC=2.4 km, BD=4.1 km, CD=3.0 km, CE=6.5 km, DE=2.8 km. The cost of laying cable is £850 per km.
(a)State the number of edges needed to connect all 5 villages in a minimum spanning tree.(1)
(b)Use Kruskal's algorithm to find a minimum spanning tree for this network, showing the order in which edges are considered and whether each is accepted or rejected.(5)
(c)Given the cost of laying cable stated above, find the total cost of connecting all 5 villages using the minimum spanning tree found in part (b).(2)
(Total for Question 6 is 8 marks)
7
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 3, AC = 34, AE = 8, BC = 37, BF = 25, CD = 28, CE = 27, CF = 13.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 7 is 7 marks)
8
The graph G has vertices A, B, C, D, E and edges AC, AE, BC, BD, BE, CD.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K6 has 6 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 8 is 8 marks)
9
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 16, AF = 23, BC = 36, BD = 38, BE = 33, BG = 24, CE = 10, DE = 5, FG = 19.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 9 is 7 marks)
10
The graph G has vertices A, B, C, D, E, F and edges AC, AD, AE, BD, BE, BF, CD, CE, EF.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K7 has 7 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 10 is 8 marks)
11
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 23, AE = 16, AG = 4, BG = 15, CE = 5, CF = 18, CG = 39, DE = 27, DF = 12, DG = 35, EF = 11.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 11 is 7 marks)
12
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 9, AC = 5, AE = 38, AG = 27, BC = 35, BG = 13, DE = 15, DF = 18, EF = 36, EG = 12.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 12 is 7 marks)
13
The graph G has vertices A, B, C, D, E, F, G and edges AB, AG, BE, CD, CE, CF, CG, DE, EF, FG.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K7 has 7 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 13 is 8 marks)
14
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AD = 11, AE = 18, BC = 10, BE = 30, BG = 35, CF = 23, CG = 33, DF = 39, DG = 6, EF = 29, FG = 5.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 14 is 7 marks)
15
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AC = 8, AD = 37, BC = 15, BD = 9, BF = 31, BG = 10, CD = 5, CE = 17, CF = 24, CG = 18, DG = 11.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 15 is 7 marks)
16
The graph G has vertices A, B, C, D, E, F, G and edges AB, AG, BF, CD, CF, CG, DE, DF, EG.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K5 has 5 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 16 is 8 marks)
17
A network has vertices A, B, C, D, E, F and the following weighted arcs: AD = 21, AF = 31, BC = 30, BE = 3, BF = 38, CD = 23, CE = 7, CF = 24, DE = 26.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 17 is 7 marks)
18
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AB = 32, AC = 37, AD = 7, AE = 39, AG = 16, CE = 23, CF = 9, CG = 34, DF = 22, EF = 17, FG = 30.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 18 is 7 marks)
19
A network has vertices A, B, C, D, E, F, G and the following weighted arcs: AC = 7, AE = 17, BD = 24, CD = 10, CE = 11, DF = 34, DG = 38, EF = 4, EG = 9, FG = 26.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 19 is 7 marks)
20
The graph G has vertices A, B, C, D, E and edges AB, AD, AE, BC, BD, BE, DE.
(a)Find the degree of each vertex, and verify the handshaking lemma for G.(3)
(b)Classify G as Eulerian, semi-Eulerian or neither, giving a reason.(2)
(c)The complete graph K7 has 7 vertices, each joined to every other. Find its number of edges, and state whether it is Eulerian.(3)
(Total for Question 20 is 8 marks)
21
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 21, AD = 31, AE = 28, AF = 24, BC = 7, BD = 12, BF = 18, CD = 3, CE = 13, DE = 36.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 21 is 7 marks)
22
A network has vertices A, B, C, D, E, F and the following weighted arcs: AB = 12, AC = 22, AD = 28, AF = 3, BD = 13, BE = 30, CD = 9, CF = 29, DE = 32, DF = 37.
(a)Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which you add them to the tree.(3)
(b)State the total weight of your minimum spanning tree.(1)
(c)Use Prim's algorithm starting at vertex A to find the minimum spanning tree, listing the arcs in the order added.(3)
(Total for Question 22 is 7 marks)
23
A network of relay stations A, B, C, D, E, F, G is to be connected by fibre-optic cable. The possible direct links and their lengths, in km, are: AB=5, AC=8, AD=10, BC=3, BE=7, CD=4, CE=6, CF=9, DF=5, EF=2, EG=8, FG=3. Kruskal's algorithm is to be used to find a minimum spanning tree for this network.
(a)State the two key steps of Kruskal's algorithm for finding a minimum spanning tree.(2)
(b)Apply Kruskal's algorithm to the network, listing the edges in the order they are considered and stating whether each is accepted or rejected.(5)
(c)State the total weight of the minimum spanning tree found in part (b).(1)
(d)Verify that the tree found in part (b) uses the correct number of edges for a spanning tree of this network.(1)
(e)A new relay station, H, is to be added, connected only to G by a new link GH = 5 km, at a cost of £3000 per km. State the new total weight of the minimum spanning tree once H is included, and find the total cost of the resulting network.(2)
(Total for Question 23 is 11 marks)
24
The table below shows the direct distances, in km, between six market towns A, B, C, D, E, F that a regional council wishes to connect with a new fibre-optic network, following existing roads only where a distance is given (a dash indicates no direct road).
ABCDEF
A-12-9-14
B12-7-11-
C-7-6108
D9-6-5-
E-11105-4
F14-8-4-
(a)State the number of edges required in a minimum spanning tree connecting all 6 towns.(1)
(b)Use Prim's algorithm, starting at A, to find a minimum spanning tree for this network. Show, at each stage, the town added to the tree and the length of road used to connect it.(9)
(c)State the total length of cable required for the minimum spanning tree found in part (b).(1)
(d)Verify your answer to part (c) by applying Kruskal's algorithm to the same network and comparing the total weight obtained.(2)
(Total for Question 24 is 13 marks)
Mark scheme · 4.2 Decision Maths: Graphs, Trees and Minimum Spanning Trees

Question 1

  • (a) n - 1 caoB1
  • (a) Answer: n - 1
  • (b) using the handshaking lemma, sum of degrees = 2 x (number of edges)M1
  • (b) = 2(n - 1) cso, using the result from part (a) that the tree has n - 1 edgesA1
  • (b) Answer: Sum of degrees = 2(n - 1).
  • (c) number of edges = 15 - 1 = 14M1
  • (c) 28 cao (sum of degrees = 2 x 14)A1
  • (c) Answer: 28

Question 2

  • (a) the sum of the degrees of all the vertices of a graph equals twice the number of edges (oe)B1
  • (a) Answer: Sum of degrees = 2 x (number of edges).
  • (b) sum of degrees = 2 x 11M1
  • (b) 22 caoA1
  • (b) Answer: 22
  • (c) sum of degrees = 4 + 3 + 3 + 2 + 2 + 1 + 1 (= 16)M1
  • (c) 8 cao (edges = 16/2)A1
  • (c) Answer: 8
  • (d) the sum of all degrees is always even (= 2|E|); removing the even-degree vertices (which contribute an even amount) leaves the sum of the odd degrees, which must also be even, and a sum of odd numbers is only even if there is an even number of them (oe)B1
  • (d) Answer: The number of odd-degree vertices must be even.

Question 3

  • (a) edges from the matrix correctly listed: KL=6, KN=9, LM=5, LN=7, MN=4M1
  • (a) edges sorted into ascending order: MN(4), LM(5), KL(6), LN(7), KN(9)M1
  • (a) MN, LM, KL correctly accepted in order; LN and KN correctly rejected as each would form a cycleA1
  • (a) total weight = 15 (km) caoA1
  • (a) Answer: Minimum spanning tree = {KL, LM, MN}, weight 15 km.
  • (b) LN(7) and KN(9) correctly identified as the two edges not requiredB1
  • (b) LN(7) exceeds both edges on L-M-N (5,4); KN(9) exceeds every edge on K-L-M-N (6,5,4). To retain a spanning tree after adding either edge, remove an edge on its resulting cycle. Every valid replacement therefore increases the total weight, so neither can reduce it (oe).B1
  • (b) Answer: LN(7) and KN(9) are not required.

Question 4

  • (a) n - 1 caoB1
  • (a) Answer: n - 1
  • (b) 8 caoB1
  • (b) Answer: 8
  • (c) 13 caoB1
  • (c) Answer: 13
  • (d) a spanning tree of the network has 10 - 1 = 9 edgesM1
  • (d) 6 cao (15 - 9)A1
  • (d) Answer: 6

Question 5

  • (a) edges sorted into ascending order: AB(3), AC(3), BD(4), CD(4), BC(5)M1
  • (a) AB and AC both correctly accepted, then either BD or CD correctly accepted to complete a 3-edge treeM1
  • (a) 10 (km) caoA1
  • (a) Answer: 10 km
  • (b) {AB, AC, BD} correctly identified as one minimum spanning tree of weight 10B1
  • (b) {AB, AC, CD} correctly identified as a second minimum spanning tree of weight 10, with explanation that BD and CD have equal weight (4), so either may be chosen without changing the total weight (oe)B1
  • (b) Answer: {AB, AC, BD} and {AB, AC, CD}, both of weight 10.
  • (c) Yes; since BD and CD both have weight 4, Prim's algorithm could select either edge when connecting D, so it could produce either of the two trees (oe)B1
  • (c) Answer: Yes; the tie between BD and CD means either tree could result.

Question 6

  • (a) 4 caoB1
  • (a) Answer: 4
  • (b) edges sorted into ascending order: BC(2.4), DE(2.8), CD(3.0), AB(3.2), BD(4.1), AC(5.6), CE(6.5)M1
  • (b) BC and DE each correctly accepted (no cycle)M1
  • (b) CD correctly accepted, joining the two separate components {B,C} and {D,E}M1
  • (b) AB correctly accepted, completing the tree; BD, AC, CE correctly rejected or not requiredA1
  • (b) total weight = 11.4 (km) caoA1
  • (b) Answer: Minimum spanning tree = {AB, BC, CD, DE}, weight 11.4 km.
  • (c) 11.4 x 850 (ft their weight from part (b))M1
  • (c) £9690 caoA1
  • (c) Answer: £9690

Question 7

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: AB (3), AE (8), CF (13), BF (25), CD (28)A1
  • (a) Answer: AB (3), AE (8), CF (13), BF (25), CD (28)
  • (b) 77B1
  • (b) Answer: 77
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AB (3), AE (8), BF (25), CF (13), CD (28)A1
  • (c) Answer: AB (3), AE (8), BF (25), CF (13), CD (28)

Question 8

  • (a) counts the edges at each vertexM1
  • (a) degrees: A 2, B 3, C 3, D 2, E 2A1
  • (a) sum of degrees = 12 = 2 x 6 edgesA1
  • (a) Answer: A 2, B 3, C 3, D 2, E 2; sum 12
  • (b) counts the vertices of odd degree: B, CM1
  • (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
  • (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
  • (c) 6(6 - 1)/2M1
  • (c) 15 edgesA1
  • (c) each vertex has degree 5, which is odd, so K6 is not EulerianB1
  • (c) Answer: 15 edges; not Eulerian

Question 9

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: DE (5), CE (10), AB (16), FG (19), AF (23), BE (33)A1
  • (a) Answer: DE (5), CE (10), AB (16), FG (19), AF (23), BE (33)
  • (b) 106B1
  • (b) Answer: 106
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AB (16), AF (23), FG (19), BE (33), DE (5), CE (10)A1
  • (c) Answer: AB (16), AF (23), FG (19), BE (33), DE (5), CE (10)

Question 10

  • (a) counts the edges at each vertexM1
  • (a) degrees: A 3, B 3, C 3, D 3, E 4, F 2A1
  • (a) sum of degrees = 18 = 2 x 9 edgesA1
  • (a) Answer: A 3, B 3, C 3, D 3, E 4, F 2; sum 18
  • (b) counts the vertices of odd degree: A, B, C, DM1
  • (b) neither Eulerian nor semi-EulerianA1
  • (b) Answer: neither Eulerian nor semi-Eulerian
  • (c) 7(7 - 1)/2M1
  • (c) 21 edgesA1
  • (c) each vertex has degree 6, which is even, so K7 is EulerianB1
  • (c) Answer: 21 edges; Eulerian

Question 11

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: AG (4), CE (5), EF (11), DF (12), BG (15), AE (16)A1
  • (a) Answer: AG (4), CE (5), EF (11), DF (12), BG (15), AE (16)
  • (b) 63B1
  • (b) Answer: 63
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AG (4), BG (15), AE (16), CE (5), EF (11), DF (12)A1
  • (c) Answer: AG (4), BG (15), AE (16), CE (5), EF (11), DF (12)

Question 12

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: AC (5), AB (9), EG (12), BG (13), DE (15), DF (18)A1
  • (a) Answer: AC (5), AB (9), EG (12), BG (13), DE (15), DF (18)
  • (b) 72B1
  • (b) Answer: 72
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AC (5), AB (9), BG (13), EG (12), DE (15), DF (18)A1
  • (c) Answer: AC (5), AB (9), BG (13), EG (12), DE (15), DF (18)

Question 13

  • (a) counts the edges at each vertexM1
  • (a) degrees: A 2, B 2, C 4, D 2, E 4, F 3, G 3A1
  • (a) sum of degrees = 20 = 2 x 10 edgesA1
  • (a) Answer: A 2, B 2, C 4, D 2, E 4, F 3, G 3; sum 20
  • (b) counts the vertices of odd degree: F, GM1
  • (b) semi-Eulerian (has an Eulerian trail but no cycle)A1
  • (b) Answer: semi-Eulerian (has an Eulerian trail but no cycle)
  • (c) 7(7 - 1)/2M1
  • (c) 21 edgesA1
  • (c) each vertex has degree 6, which is even, so K7 is EulerianB1
  • (c) Answer: 21 edges; Eulerian

Question 14

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: FG (5), DG (6), BC (10), AD (11), AE (18), CF (23)A1
  • (a) Answer: FG (5), DG (6), BC (10), AD (11), AE (18), CF (23)
  • (b) 73B1
  • (b) Answer: 73
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AD (11), DG (6), FG (5), AE (18), CF (23), BC (10)A1
  • (c) Answer: AD (11), DG (6), FG (5), AE (18), CF (23), BC (10)

Question 15

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: CD (5), AC (8), BD (9), BG (10), CE (17), CF (24)A1
  • (a) Answer: CD (5), AC (8), BD (9), BG (10), CE (17), CF (24)
  • (b) 73B1
  • (b) Answer: 73
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AC (8), CD (5), BD (9), BG (10), CE (17), CF (24)A1
  • (c) Answer: AC (8), CD (5), BD (9), BG (10), CE (17), CF (24)

Question 16

  • (a) counts the edges at each vertexM1
  • (a) degrees: A 2, B 2, C 3, D 3, E 2, F 3, G 3A1
  • (a) sum of degrees = 18 = 2 x 9 edgesA1
  • (a) Answer: A 2, B 2, C 3, D 3, E 2, F 3, G 3; sum 18
  • (b) counts the vertices of odd degree: C, D, F, GM1
  • (b) neither Eulerian nor semi-EulerianA1
  • (b) Answer: neither Eulerian nor semi-Eulerian
  • (c) 5(5 - 1)/2M1
  • (c) 10 edgesA1
  • (c) each vertex has degree 4, which is even, so K5 is EulerianB1
  • (c) Answer: 10 edges; Eulerian

Question 17

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: BE (3), CE (7), AD (21), CD (23), CF (24)A1
  • (a) Answer: BE (3), CE (7), AD (21), CD (23), CF (24)
  • (b) 78B1
  • (b) Answer: 78
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AD (21), CD (23), CE (7), BE (3), CF (24)A1
  • (c) Answer: AD (21), CD (23), CE (7), BE (3), CF (24)

Question 18

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: AD (7), CF (9), AG (16), EF (17), DF (22), AB (32)A1
  • (a) Answer: AD (7), CF (9), AG (16), EF (17), DF (22), AB (32)
  • (b) 103B1
  • (b) Answer: 103
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AD (7), AG (16), DF (22), CF (9), EF (17), AB (32)A1
  • (c) Answer: AD (7), AG (16), DF (22), CF (9), EF (17), AB (32)

Question 19

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: EF (4), AC (7), EG (9), CD (10), CE (11), BD (24)A1
  • (a) Answer: EF (4), AC (7), EG (9), CD (10), CE (11), BD (24)
  • (b) 65B1
  • (b) Answer: 65
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AC (7), CD (10), CE (11), EF (4), EG (9), BD (24)A1
  • (c) Answer: AC (7), CD (10), CE (11), EF (4), EG (9), BD (24)

Question 20

  • (a) counts the edges at each vertexM1
  • (a) degrees: A 3, B 4, C 1, D 3, E 3A1
  • (a) sum of degrees = 14 = 2 x 7 edgesA1
  • (a) Answer: A 3, B 4, C 1, D 3, E 3; sum 14
  • (b) counts the vertices of odd degree: A, C, D, EM1
  • (b) neither Eulerian nor semi-EulerianA1
  • (b) Answer: neither Eulerian nor semi-Eulerian
  • (c) 7(7 - 1)/2M1
  • (c) 21 edgesA1
  • (c) each vertex has degree 6, which is even, so K7 is EulerianB1
  • (c) Answer: 21 edges; Eulerian

Question 21

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: CD (3), BC (7), CE (13), BF (18), AB (21)A1
  • (a) Answer: CD (3), BC (7), CE (13), BF (18), AB (21)
  • (b) 62B1
  • (b) Answer: 62
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AB (21), BC (7), CD (3), CE (13), BF (18)A1
  • (c) Answer: AB (21), BC (7), CD (3), CE (13), BF (18)

Question 22

  • (a) sorts the arcs in increasing order of weight and selects the smallestM1
  • (a) adds each next smallest arc that does not form a cycleM1
  • (a) arcs selected: AF (3), CD (9), AB (12), BD (13), BE (30)A1
  • (a) Answer: AF (3), CD (9), AB (12), BD (13), BE (30)
  • (b) 67B1
  • (b) Answer: 67
  • (c) starts at A and adds the shortest arc joining a tree vertex to a non-tree vertex each timeM1
  • (c) first three arcs correctA1
  • (c) arcs added: AF (3), AB (12), BD (13), CD (9), BE (30)A1
  • (c) Answer: AF (3), AB (12), BD (13), CD (9), BE (30)

Question 23

  • (a) consider the edges in ascending order of weight (oe)B1
  • (a) an edge is added unless it would form a cycle with edges already selected; the process stops once all vertices are connected, i.e. n - 1 edges have been chosen (oe)B1
  • (a) Answer: Sort edges by ascending weight; add each edge unless it forms a cycle, stopping once n - 1 edges have been chosen.
  • (b) edges sorted into ascending order: EF(2), BC(3), FG(3), CD(4), AB(5), DF(5), CE(6), BE(7), AC(8), EG(8), CF(9), AD(10)M1
  • (b) EF, BC, FG, CD each correctly accepted, forming no cycle with the edges already chosenM1
  • (b) AB correctly accepted, then DF correctly accepted as it joins the two separate components {A,B,C,D} and {E,F,G} (oe)M1
  • (b) remaining edges CE, BE, AC, EG, CF, AD all correctly rejected, each forming a cycle with edges already acceptedA1
  • (b) final minimum spanning tree correctly stated as {AB, BC, CD, DF, EF, FG}, using 6 edges to connect all 7 verticesA1
  • (b) Answer: Minimum spanning tree: {AB, BC, CD, DF, EF, FG}.
  • (c) 22 (km) ft their tree from part (b)B1
  • (c) Answer: 22 km
  • (d) 6 edges are used, and 7 - 1 = 6, so the number of edges is consistent with a spanning tree of a 7-vertex network caoB1
  • (d) Answer: 6 edges = 7 - 1, so the tree is a valid spanning tree.
  • (e) new total weight = 22 + 5 = 27 (ft their part (c))M1
  • (e) cost = 27 x 3000 = £81,000 caoA1
  • (e) Answer: New weight = 27 km; total cost = £81 000.

Question 24

  • (a) 5 caoB1
  • (a) Answer: 5
  • (b) AD=9 selected, D added (rejecting AB=12, AF=14)M1
  • (b) DE=5 selected, E added (comparing AB=12, AF=14, DC=6, DE=5)M1
  • (b) EF=4 selected, F addedM1
  • (b) DC=6 selected, C added (rejecting EC=10, EB=11, FC=8)M1
  • (b) BC=7 selected, B added (rejecting AB=12, EB=11)A1
  • (b) correct order of towns added stated: D, E, F, C, BA1
  • (b) correct final edge set stated: {AD, DE, EF, DC, BC}A1
  • (b) correct method shown of eliminating (crossing out) the column of any town already in the tree when searching for the next minimum entry (oe)B1
  • (b) tree confirmed to use 5 edges connecting all 6 towns with no cyclesB1
  • (b) Answer: Order of addition: D, E, F, C, B. Tree = {AD, DE, EF, DC, BC}.
  • (c) 31 (km) ft their tree from part (b)B1
  • (c) Answer: 31 km
  • (d) Kruskal's algorithm correctly applied: EF(4), DE(5), CD(6), BC(7) accepted in order; CF(8) rejected as it would form a cycle; AD(9) acceptedM1
  • (d) total = 31 (km), matching part (c) and confirming the minimum spanning tree weight caoA1
  • (d) Answer: Kruskal's algorithm also gives 31 km, confirming part (c).

Mark your answers

Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.

Question 1

5 marks
Did your answer earn the marks?

Question 2

6 marks
Did your answer earn the marks?

Question 3

6 marks
Did your answer earn the marks?

Question 4

5 marks
Did your answer earn the marks?

Question 5

6 marks
Did your answer earn the marks?

Question 6

8 marks
Did your answer earn the marks?

Question 7

7 marks
Did your answer earn the marks?

Question 8

8 marks
Did your answer earn the marks?

Question 9

7 marks
Did your answer earn the marks?

Question 10

8 marks
Did your answer earn the marks?

Question 11

7 marks
Did your answer earn the marks?

Question 12

7 marks
Did your answer earn the marks?

Question 13

8 marks
Did your answer earn the marks?

Question 14

7 marks
Did your answer earn the marks?

Question 15

7 marks
Did your answer earn the marks?

Question 16

8 marks
Did your answer earn the marks?

Question 17

7 marks
Did your answer earn the marks?

Question 18

7 marks
Did your answer earn the marks?

Question 19

7 marks
Did your answer earn the marks?

Question 20

8 marks
Did your answer earn the marks?

Question 21

7 marks
Did your answer earn the marks?

Question 22

7 marks
Did your answer earn the marks?

Question 23

11 marks
Did your answer earn the marks?

Question 24

13 marks
Did your answer earn the marks?
Mark my answers

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk