AQA A-Level Further Maths
Language and properties of graphs
Total 27 marks
Name
Class
Date
- 1A graph has vertices and seven edges: , , , , , and .(a)Write down the degree of vertex .[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(b)Which statement about is correct?[1 mark]- A is Eulerian, because every vertex has even degree
- B is Eulerian, because it is connected and contains a cycle
- C is neither Eulerian nor semi-Eulerian, because it has a vertex of degree
- D is semi-Eulerian, because exactly two vertices ( and ) have odd degree
Show the mark scheme
Mark scheme
Answer: D(c)Write down a trail in that uses every edge exactly once.[2 marks]Show the mark scheme
Mark scheme
M1: a trail that starts at and ends at (or starts at and ends at )
A1: all seven edges used exactly once, e.g.
Accept: any valid Eulerian trail, such asTotal for question 1: 4 marks
- 2A graph has vertices and eight edges: , , , , , , and .(a)How many vertices of have odd degree?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)Which of these is a Hamiltonian cycle of ?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)Explain why is neither Eulerian nor semi-Eulerian.[2 marks]Show the mark scheme
Mark scheme
M1: , , and have odd degree (degree ), so there are four odd vertices
A1: an Eulerian graph has no odd vertices and a semi-Eulerian graph has exactly two, so is neitherTotal for question 2: 4 marks
- 3A connected simple graph has six vertices. Five of the vertices have degrees and , and the sixth vertex has degree .(a)Show that is even, and state with a reason whether is Eulerian, semi-Eulerian or neither.[3 marks]
Show the mark scheme
Mark scheme
B1: the sum of the degrees equals twice the number of edges, so it is even
M1: is even, so is even
A1: exactly two vertices (the two of degree ) have odd degree, so is semi-Eulerian (not Eulerian)(b)Given that :[4 marks]
(i) find the number of edges of ;
(ii) a new graph is formed by subdividing one edge of with a new vertex. State the number of vertices and the number of edges of .Show the mark scheme
Mark scheme
M1: (i) , and the number of edges is half of this
A1: (i) edges
B1: (ii) vertices
B1: (ii) edges (one edge is replaced by two)Total for question 3: 7 marks
- 4A park has six junctions and joined by seven paths: , , , , , and .(a)(i) Show that there is a route that uses every path exactly once, and write one down.[6 marks]
(ii) Explain why no such route can start and finish at the same junction, and suggest one extra path that would make this possible.Show the mark scheme
Mark scheme
M1: (i) degrees: and have degree and , , , have degree
A1: (i) the graph is connected with exactly two odd vertices, so it is semi-Eulerian and the route exists
B1: (i) a valid trail starting at and ending at (or the reverse), e.g.
R1: (ii) a closed route needs every vertex to have even degree, but and have odd degree
M1: (ii) a second path joining and
A1: (ii) the degrees of and become , so all degrees are even and the graph is Eulerian(b)(i) Show that the graph is Hamiltonian.[6 marks]
(ii) The junction and its two paths are closed. For the network that remains, determine whether it is Eulerian, semi-Eulerian or neither, and whether it is Hamiltonian.Show the mark scheme
Mark scheme
B1: (i) a cycle through all six junctions, e.g.
B1: (i) every junction appears once, and the cycle returns to using
M1: (ii) degrees: , , , ,
A1: (ii) exactly two odd vertices ( and ) and connected, so semi-Eulerian
R1: (ii) has degree , and a cycle needs two edges at every vertex it contains, so cannot be on a cycle
A1: (ii) the network is not HamiltonianTotal for question 4: 12 marks
End of questions