Lesson 7.04e-f

7.04e-f Route inspection and choosing a network algorithm Quiz: OCR Further Maths, Unit 4

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 7.04e-f, Route inspection and choosing a network algorithm: 20 multiple choice questions for the OCR Further Maths (H245), Unit 4: Discrete Mathematics (Y544), 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. What property must a graph possess to contain an Eulerian trail?

    • All vertices even
    • All vertices odd
    • At least four
    • Exactly three odd

  2. According to the Handshaking Lemma, how many odd vertices can a graph contain?

    • An even number
    • Any number
    • An odd number
    • At least three

  3. If a graph has 4 odd vertices, how many distinct pairings of these vertices exist?

    • 4
    • 6
    • 3
    • 12

  4. What is the primary objective of the Route Inspection Algorithm on a weighted network?

    • Find shortest tree
    • Visit vertices once
    • Maximise total weight
    • Minimise traversal length

  5. Which algorithm finds the minimum spanning tree of a network by considering edges in order of weight?

    • Dijkstra's algorithm
    • Kruskal's algorithm
    • Nearest neighbour algorithm
    • Route inspection algorithm

  6. Which algorithm is best suited for finding the shortest path between two specific network nodes?

    • Kruskal's algorithm
    • Prim's algorithm
    • Route inspection algorithm
    • Dijkstra's algorithm

  7. Which problem involves visiting every vertex in a graph exactly once and returning to the start?

    • Minimum Connector Problem
    • Shortest Path Problem
    • Route Inspection Problem
    • Travelling Salesperson Problem

  8. In a connected graph with exactly two odd vertices, how many paths must be repeated?

    • 0
    • 3
    • 2
    • 1

  9. A network has total weight 50 and repeated edges with weight 12. What is the route length?

    • 62
    • 74
    • 38
    • 50

  10. A connected graph has vertex degrees 2, 2, 3, 3, and 4. How many odd vertices are there?

    • 2
    • 5
    • 3
    • 4

  11. If odd vertices are A, B, C, and D, which option represents a valid pairing?

    • AC and AD
    • AB and BC
    • AB and AC
    • AB and CD

  12. For odd vertices A, B, C, D, path sums are AB+CD=8, AC+BD=11, AD+BC=14. What is the minimum added weight?

    • 14
    • 8
    • 33
    • 11

  13. How many distinct pairings can be formed from a graph with 6 odd vertices?

    • 15
    • 10
    • 30
    • 6

  14. What happens to the degree of odd vertices after adding repeated paths in route inspection?

    • They remain odd
    • They become zero
    • They double
    • They become even

  15. Which algorithm determines the shortest route covering every road in a gritted district network?

    • Dijkstra's algorithm
    • Prim's algorithm
    • Kruskal's algorithm
    • Route inspection algorithm

  16. Which algorithm connects all houses in a street with broadband cable using minimum cable length?

    • Route inspection algorithm
    • Nearest neighbour algorithm
    • Prim's algorithm
    • Dijkstra's algorithm

  17. A graph has total edge weight 140 and minimum repeated edges sum to 18. What is the route inspection length?

    • 140
    • 158
    • 122
    • 176

  18. What is another standard name for the Route Inspection Algorithm?

    • Travelling Salesperson Problem
    • Shortest Path Algorithm
    • Chinese Postman Algorithm
    • Minimum Spanning Algorithm

  19. In a graph with degree sequence 3, 3, 3, 3, 2, how many odd vertices require pairing?

    • 4
    • 5
    • 2
    • 3

  20. If a connected graph has zero odd vertices, how many edges must be repeated in route inspection?

    • 2
    • 0
    • 4
    • 1

All OCR Further Maths quizzes