D1.1.3 Use of the order of the nodes to determine whether a graph is…

Section
D1.1 Algorithms and graph theory
Level
AS & A level
Statement
Use of the order of the nodes to determine whether a graph is Eulerian, semi- Eulerian or neither.
Guidance
Students will be expected to be familiar with the following types of graphs: complete (including K notation), planar and isomorphic.
Since 2018
21 parts, 38 marks · topic pages: Algorithms, sorting, bin packing and graph theory

Back to the checklist

June 2025 · AS Paper 2 (Decision 1) · Q3(a) 1 mark
3 B H A F C J E G Figure 2 [The total weight of the network is 153] Figure 2 models a network of roads in a town, where the nodes represent road junctions. The numbers on the edges are the times, in minutes, taken to walk along the corresponding roads. (a) State, with a reason, whether the graph in Figure 2 is Eulerian, semi-Eulerian or neither. (1)
June 2024 · AS Paper 2 (Decision 1) · Q3(a) 1 mark
3. K F B y C G M A H x L E J Figure 3 [The total weight of the network is 139 + x + y] (a) Explain what is meant by the term “tree”. (1)
June 2024 · Paper 3D (Decision 1) · Q4(a) 1 mark
4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 (1)
June 2024 · Paper 3D (Decision 1) · Q4(b) 1 mark
A tree, T, has exactly six nodes. The degrees of the six nodes of T are (4 – x) (2x – 5) (4x – 11) (3x – 5) where x is an integer. (b) Explain how you know that T cannot be Eulerian. (1)
June 2024 · Paper 3D (Decision 1) · Q4(c) 5 marks
(c) (i) Determine the value of x (ii) Hence state whether T is semi-Eulerian or not. You must justify your answer. (5)
June 2024 · Paper 3D (Decision 1) · Q4(d) 1 mark
Figure 2 Figure 2 shows a graph, G, with six nodes with degrees 1, 2, 3, 3, 3 and 4 (d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees 1, 2, 3, 3, 3 and 4 that is not isomorphic to G. (1)
June 2023 · AS Paper 2 (Decision 1) · Q5(a) 1 mark
5. B x + 4 2x + 1 5x – 8 2x – 2 C A x + 5 3x + 2 x + 7 E 5x – 6 F Figure 4 [The weight of the network is 20x + 3] Figure 4 shows a graph G that contains 8 arcs and 6 vertices. (a) State the minimum number of arcs that would need to be added to make G into an Eulerian graph. (1)
June 2023 · AS Paper 2 (Decision 1) · Q5(b) 1 mark
(b) Explain whether or not the route A – C – F – E – C – D – B is an example of a path on G. (1)
June 2023 · Paper 3D (Decision 1) · Q1(a) 1 mark
1. E A B C Figure 1 Figure 1 shows the graph G. (a) State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q1(c) 1 mark
(c) State whether or not G is planar, justifying your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q1(d) 1 mark
(d) State the number of arcs that would need to be added to G to make the graph K5 (1)
June 2022 · AS Paper 2 (Decision 1) · Q3(a) 2 marks
3. B E C H A F G Figure 2 [The total weight of the network is 120] (a) Explain what is meant by the term “path”. (2)
June 2022 · AS Paper 2 (Decision 1) · Q3(b) 1 mark
(b) State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither. (1)
Oct 2020 · AS Paper 2 (Decision 1) · Q3(a) 2 marks
3. B C E 2x + 10 A F 3x – 2 G H Figure 2 [The weight of the network is 5x + 246] (a) Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. (2)
Oct 2020 · Paper 3D (Decision 1) · Q6(a) 2 marks
6. E B x F A C y G Figure 4 [The total weight of the network is 320 + x + y] (a) State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. (2)
June 2019 · AS Paper 2 (Decision 1) · Q1(a) 1 mark
1. (a) Draw the graph K5 (1)
June 2019 · AS Paper 2 (Decision 1) · Q1(b) 3 marks
(b) (i) In the context of graph theory explain what is meant by ‘semi-Eulerian’. (ii) Draw two semi-Eulerian subgraphs of K5, each having five vertices but with a different number of edges. (3)
June 2019 · AS Paper 2 (Decision 1) · Q1(c) 2 marks
(c) Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. (2)
June 2018 · AS Paper 2 (Decision 1) · Q2(a) 2 marks
2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. (a) Given that a simply connected graph has exactly four vertices, (i) write down the minimum number of arcs it can have, (ii) write down the maximum number of arcs it can have. (2)
June 2018 · AS Paper 2 (Decision 1) · Q2(b)(i) 3 marks
(b) (i) Draw a simply connected graph that has exactly four vertices and exactly five arcs. (ii) State, with justification, whether your graph is Eulerian, semi-Eulerian or neither. (3)
June 2018 · AS Paper 2 (Decision 1) · Q2(c) 5 marks
(c) By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs. (5)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.