Lesson 3D.2.1

3D.2.1 Minimum spanning trees: Prim's and Kruskal's algorithms Quiz: Pearson Edexcel Further Maths, Unit 36

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 3D.2.1, Minimum spanning trees: Prim's and Kruskal's algorithms: 20 multiple choice questions for the Pearson Edexcel Further Maths (9FM0), Unit 36: Algorithms on graphs, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. A spanning tree of a graph with n vertices has how many edges?

    • n(n - 1)/2
    • n + 1
    • n - 1
    • n

  2. In Kruskal's algorithm, the next edge added at each step is

    • the cheapest edge leaving the starting vertex
    • the edge with the most vertices
    • the cheapest edge that does not create a cycle
    • the most expensive edge available

  3. In Prim's algorithm the tree grows by

    • adding the most expensive edge joining two vertices
    • removing the most expensive edge
    • adding the cheapest edge anywhere, even if it forms a cycle
    • adding the cheapest edge joining the tree to a vertex not yet in it

  4. A minimum spanning tree is a spanning tree with

    • the largest total weight
    • the fewest vertices
    • the smallest possible total weight
    • the most edges

  5. In the matrix representation used for Prim's algorithm, each entry holds

    • the degree of each vertex
    • the weight of the edge, with a symbol where there is no direct edge
    • the paths between vertices
    • the number of vertices

  6. A tree is a connected graph with

    • every vertex of degree 2
    • more edges than vertices
    • no cycles
    • exactly one odd vertex

  7. A spanning tree must include

    • only the vertices of odd degree
    • exactly half of the edges
    • all the vertices of the graph
    • only the cheapest edges

  8. A network has edges AB 2, BC 3, AC 4, CD 5 and BD 6. What is the total weight of its minimum spanning tree?

    • 10
    • 14
    • 11
    • 9

  9. Prim's algorithm starts at vertex A in the network with edges AB 2, BC 3, AC 4, CD 5 and BD 6. Which edge is added first?

    • AC, weight 4
    • BD, weight 6
    • CD, weight 5
    • AB, weight 2

  10. A minimum spanning tree on 5 vertices uses edges of weights 2, 2, 3 and 5. What is its total weight?

    • 12
    • 15
    • 13
    • 9

  11. A network has edges XY 1, YZ 1, XZ 1, XW 3 and ZW 2. What is the weight of its minimum spanning tree?

    • 3
    • 6
    • 5
    • 4

  12. Which algorithm builds a minimum spanning tree by sorting all the edges by weight?

    • Floyd's algorithm
    • Kruskal's algorithm
    • Dijkstra's algorithm
    • Prim's algorithm

  13. A square of side 1 has a diagonal of length 1.5, and its four vertices are joined by the sides and the diagonal. What is the weight of a minimum spanning tree?

    • 2.5
    • 4
    • 3
    • 3.5

  14. Edges AB 1, BC 2, CA 2 and CD 4 form a network. What is the weight of its minimum spanning tree?

    • 7
    • 5
    • 9
    • 8

  15. Prim's algorithm starts at A with edges AB 3, AD 6, BD 2, BC 4 and DC 5. After the tree contains A, B and D, which edge is added next?

    • AB, weight 3
    • DC, weight 5
    • BC, weight 4
    • AD, weight 6

  16. When all edge weights are distinct, is the minimum spanning tree of a connected network unique?

    • Yes, it is unique
    • No, there are always two
    • Yes, but only for trees with three vertices
    • No, the number depends on the number of vertices

  17. Kruskal's and Prim's algorithms both find minimum spanning trees. Why do they always give the same total weight?

    • They always produce identical trees
    • Prim's algorithm always gives a larger weight
    • Both are greedy algorithms whose choices always keep an edge of some minimum spanning tree, so the minimum total weight is the same
    • They only work on graphs with unique weights

  18. Within a cycle in a network with all weights distinct, which edge is excluded from the minimum spanning tree?

    • the first edge listed in the cycle
    • the edge that touches the start vertex
    • the heaviest edge of the cycle
    • the lightest edge of the cycle

  19. Why does a tree on n vertices have exactly n - 1 edges?

    • each vertex has degree 2
    • It is connected and acyclic, so each vertex after the first joins by exactly one edge
    • each edge uses two vertices, so there are n/2 edges
    • a tree is a complete graph

  20. A network has edges AB 4, AC 3, BC 5, BD 6, CD 2, DE 7 and CE 8. What is the total weight of its minimum spanning tree?

    • 17
    • 19
    • 16
    • 15

All Pearson Edexcel Further Maths quizzes