plumiGraphs and networks: OCR A‑Level Further Maths questions
Every OCR A-Level Further Maths exam question on D.2 Graphs and networks, 2018–2025, with its mark scheme and examiner’s report.
Find questions648
![June 2025 Discrete Mathematics, question 2: (a) Graph G is shown below B A C F E D (i) Show that graph G is not bipartite. [2] (ii) Use Kuratowski’s Theorem to show that graph G is not planar. [3] (iii) D](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y54401-jun25-02-qp.webp?v=3)
![June 2025 AS Discrete Mathematics, question 5: Graph X is shown below. B D C A E H G F (a) Explain whether graph X is Eulerian, semi-Eulerian or neither. [1] (b) Give an example of a cycle on the graph above](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y53401-jun25-05-qp.webp?v=3)
![June 2023 Discrete Mathematics, question 2: A graph is shown below. B C A D E F (a) Write down a cycle through all six vertices. [1] (b) Write down a continuous route that uses every arc exactly once. [2]](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y54401-jun23-02-qp.webp?v=3)
![June 2023 AS Discrete Mathematics, question 2: A network is shown below. A 4 3 2 E B 15 9 5 8 2 C D (a) Use an appropriate algorithm to find the least weight (shortest) path from A to D. [3] (b) Use Kruskal’](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y53401-jun23-02-qp.webp?v=3)
![June 2023 AS Discrete Mathematics, question 4: Graph G is a simply connected Eulerian graph with 4 vertices. (a) (i) Explain why graph G cannot be a complete graph. [2] (ii) Determine the number of arcs in g](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y53401-jun23-04-qp.webp?v=3)
![June 2022 Discrete Mathematics, question 4: A connected graph is shown below. D G A F C B E H (a) Write down a path through exactly 7 of the vertices. [1] (b) Write down a cycle through exactly 6 of the v](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y54401-jun22-04-qp.webp?v=3)
![November 2021 Discrete Mathematics, question 4: One of these graphs is isomorphic to K2,3. Graph A Graph B Graph C (a) Explain how you know that each of the other graphs is not isomorphic to K2,3. [2] The arc](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y54401-nov21-04-qp.webp?v=3)
![November 2020 Discrete Mathematics, question 1: This question is about the planar graph shown below. B E D G A C F (a) (i) Apply Kuratowski’s theorem to verify that the graph is planar. [2] (ii) Use Euler’s f](https://pub-e8a9dbab8e2a4d089f52b2a45e0d0b50.r2.dev/bank/y54401-nov20-01-qp.webp?v=3)
All 26 questions on Graphs and networks, as a list
- June 2025, Discrete Mathematics, Q1 (8 marks): A coach operator offers sightseeing tours of a city. The sightseeing tour starts and ends at stop A, and there are tourist attractions at B, C, D, E, F and G. T
- June 2025, Discrete Mathematics, Q2 (9 marks): (a) Graph G is shown below B A C F E D (i) Show that graph G is not bipartite. [2] (ii) Use Kuratowski’s Theorem to show that graph G is not planar. [3] (iii) D
- June 2025, AS Discrete Mathematics, Q3 (9 marks): The table shows the lengths in km of footpaths between six places, A to F, in a town. A B C D E F A – 5 3 5 8 10 B 5 – 6 2 7 5 C 3 6 – 1 10 8 D 5 2 1 – 9 4 E 8
- June 2025, AS Discrete Mathematics, Q5 (5 marks): Graph X is shown below. B D C A E H G F (a) Explain whether graph X is Eulerian, semi-Eulerian or neither. [1] (b) Give an example of a cycle on the graph above
- June 2024, Discrete Mathematics, Q5 (18 marks): (a) Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
- June 2024, AS Discrete Mathematics, Q1 (8 marks): There are six non-isomorphic trees with exactly six vertices. A student has drawn the diagram below showing six trees each with exactly six vertices. However, t
- June 2024, AS Discrete Mathematics, Q5 (10 marks): A garden centre sells mixed packs of flower bulbs. Each pack contains bulbs which produce flowers of two different colours. The cost, in £, of a pack of each co
- June 2023, Discrete Mathematics, Q2 (8 marks): A graph is shown below. B C A D E F (a) Write down a cycle through all six vertices. [1] (b) Write down a continuous route that uses every arc exactly once. [2]
- June 2023, Discrete Mathematics, Q6 (14 marks): A graph is shown in Fig. 1.1. The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km. A
- June 2023, AS Discrete Mathematics, Q2 (6 marks): A network is shown below. A 4 3 2 E B 15 9 5 8 2 C D (a) Use an appropriate algorithm to find the least weight (shortest) path from A to D. [3] (b) Use Kruskal’
- June 2023, AS Discrete Mathematics, Q4 (10 marks): Graph G is a simply connected Eulerian graph with 4 vertices. (a) (i) Explain why graph G cannot be a complete graph. [2] (ii) Determine the number of arcs in g
- June 2022, Discrete Mathematics, Q1 (6 marks): Four children, A, B, C and D, discuss how many of the 23 birthday parties held by their classmates they had gone to. Each party was attended by at least one of
- June 2022, Discrete Mathematics, Q4 (13 marks): A connected graph is shown below. D G A F C B E H (a) Write down a path through exactly 7 of the vertices. [1] (b) Write down a cycle through exactly 6 of the v
- June 2022, Discrete Mathematics, Q7 (12 marks): A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors. The cameras at the junctions and the lengths of the 11 corridors between them,
- June 2022, AS Discrete Mathematics, Q6 (9 marks): Eight footpaths connect six villages. The lengths of these footpaths, in km, are given in the table. Villages connected A B A D B E B F C D C E D E E F Length o
- November 2021, Discrete Mathematics, Q2 (8 marks): A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4. (a) (i) Determine the minimum possible vertex degree.
- November 2021, Discrete Mathematics, Q4 (13 marks): One of these graphs is isomorphic to K2,3. Graph A Graph B Graph C (a) Explain how you know that each of the other graphs is not isomorphic to K2,3. [2] The arc
- November 2021, Discrete Mathematics, Q7 (15 marks): A network is formed by weighting the graph below using the listed arc weights. 2.9 0.9 1.5 3.5 4.2 5.3 4.7 2.3 (a) (i) Show the result after the first pass and
- November 2021, AS Discrete Mathematics, Q3 (10 marks): The diagram shows a simplified map of the main streets in a small town. B 2.1 D 0.6 0.8 0.6 1.2 F X 0.9 A Y 1.1 0.4 0.8 0.7 1.0 E C 2.0 Some of the junctions ha
- November 2020, Discrete Mathematics, Q1 (9 marks): This question is about the planar graph shown below. B E D G A C F (a) (i) Apply Kuratowski’s theorem to verify that the graph is planar. [2] (ii) Use Euler’s f
- November 2020, Discrete Mathematics, Q5 (17 marks): The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E. The ta
- November 2020, AS Discrete Mathematics, Q3 (8 marks): D B F H A G E C (a) By listing the vertices passed through, in the order they are used, give an example for the graph above of: (i) a walk from A to H that is n
- June 2019, Discrete Mathematics, Q1 (8 marks): Two graphs are shown below. A B P Q C D R S E T Graph G1 Graph G2 (a) (i) Prove that the graphs are isomorphic. [2] (ii) Verify that Euler’s formula holds for g
- June 2019, Discrete Mathematics, Q5 (14 marks): A network is represented by the distance matrix below. For this network a direct connection between two vertices is always shorter than an indirect connection.
- June 2019, AS Discrete Mathematics, Q2 (10 marks): Two graphs are shown below. J K P Q L R M N S T Graph G1 Graph G2 (a) List the vertex degrees for each graph. [3] (b) Prove that the graphs are non‑isomorphic.
- June 2018, AS Discrete Mathematics, Q4 (8 marks): The complete bipartite graph K3, 4 connects the vertices {2, 4, 6} to the vertices {1, 3, 5, 7}. (i) How many arcs does the graph K3, 4 have? [1] (ii) Deduce ho
Questions, mark schemes and examiner’s reports are © OCR, from their published past papers. Plumi isn’t affiliated with any exam board. Want whole papers? Every OCR A-Level Further Maths paper.
Rather write your answers by hand on iPad? Plumi marks them against the same mark schemes.