Lesson 3D.3.2

3D.3.2 Travelling salesman problems Quiz: Pearson Edexcel Further Maths, Unit 37

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 3D.3.2, Travelling salesman problems: 20 multiple choice questions for the Pearson Edexcel Further Maths (9FM0), Unit 37: Algorithms on graphs II, 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. In the classical travelling salesman problem, how many times is each vertex visited?

    • once only
    • at least twice
    • an unlimited number of times
    • as many times as its degree

  2. A walk that visits every vertex and returns to its starting vertex is called a

    • trail
    • cycle only
    • tour
    • path

  3. For three vertices A, B and C, the triangle inequality states that

    • length AB is at least AC plus CB
    • length AB is at most length AC plus length CB
    • length AC is at most length AB
    • length AB equals AC plus CB always

  4. The nearest neighbour algorithm moves from the current vertex to

    • the vertex with the most edges
    • the starting vertex
    • the farthest unvisited vertex
    • the nearest unvisited vertex

  5. The nearest neighbour algorithm gives

    • a minimum spanning tree
    • the exact optimal tour always
    • a lower bound on the optimal tour length
    • an upper bound on the optimal tour length

  6. A lower bound for the classical travelling salesman problem can be found by

    • running the nearest neighbour algorithm
    • adding all the edge weights together
    • removing a vertex, finding the minimum spanning tree of the rest, and adding the two shortest edges from that vertex
    • finding the minimum spanning tree of the whole network

  7. With the triangle inequality, a shortcut in a tour

    • removes a vertex from the network
    • is only valid for trees
    • always increases the total length
    • never increases the total length

  8. A triangle has sides 3, 4 and 5. What is the length of its only tour?

    • 12
    • 9
    • 8
    • 15

  9. Vertices A, B, C and D have edges AB 2, AC 4, AD 3, BC 3, BD 5 and CD 2. The nearest neighbour tour starts at A. What is its length?

    • 12
    • 10
    • 11
    • 9

  10. Which set of distances does NOT satisfy the triangle inequality?

    • AB = 4, AC = 4, CB = 4
    • AB = 6, AC = 3, CB = 3
    • AB = 7, AC = 3, CB = 3
    • AB = 5, AC = 3, CB = 4

  11. A lower bound comes from removing vertex A, leaving a minimum spanning tree of weight 9 on the other vertices. A has edges of weight 3 and 4 to those vertices. What is the lower bound?

    • 12
    • 14
    • 18
    • 16

  12. A classical tour visits 6 vertices, each once, and returns to its start. How many edges does the tour use?

    • 7
    • 6
    • 5
    • 12

  13. Nearest neighbour gives an upper bound of 22 and a lower bound is 18. What can be said about the optimal tour length?

    • It is exactly 20
    • It is greater than 22
    • It is always 22
    • It lies between 18 and 22 inclusive

  14. In a complete network built from shortest distances, the direct distance A to C is 9, but the shortest route A to B to C has length 7. What weight does the complete network assign to A-C?

    • 9
    • 7
    • 3
    • 12

  15. A minimum spanning tree of a network has weight 10. Under the triangle inequality, what upper bound does doubling this tree give for the classical tour?

    • 30
    • 20
    • 5
    • 10

  16. An upper bound of 24 and a lower bound of 21 are found for a travelling salesman problem. What is the gap between them?

    • 5
    • 2
    • 26
    • 3

  17. Why is nearest neighbour not guaranteed to give the optimal tour?

    • it cannot visit all the vertices
    • it always takes the longest edge first
    • an early greedy choice can force long edges later
    • it ignores the edge weights

  18. Why is the minimum spanning tree of the remaining vertices a lower bound in the removed-vertex argument?

    • A Hamiltonian path on the remaining vertices is a spanning tree, so its length is at least the minimum spanning tree weight
    • removing a vertex creates a cycle
    • a path always equals the spanning tree weight
    • a spanning tree has more edges than a path

  19. Why does doubling every edge of a minimum spanning tree and shortcutting give an upper bound on the optimal tour?

    • a minimum spanning tree already is a tour
    • doubling gives the exact optimal tour
    • Doubling gives a closed walk of length twice the tree weight, and shortcutting with the triangle inequality never increases its length
    • shortcutting increases the length of the walk

  20. A network has edges AB 4, AC 6, BC 3, CD 5 and BD 7. Removing vertex A, the minimum spanning tree of B, C and D has weight 8. What is the lower bound on the classical tour?

    • 14
    • 18
    • 17
    • 22

All Pearson Edexcel Further Maths quizzes