Language and properties of graphsAQA A-Level Further Maths: Subtopic test

1. 1
   A graph $G$ has vertices $A,\ B,\ C,\ D,\ E$ and seven edges: $AB$, $AC$, $BC$, $BD$, $CD$, $CE$ and $DE$.

   (a)

   Write down the degree of vertex $C$.

   [1 mark]

   • A$4$
   • B$3$
   • C$2$
   • D$7$

   (b)

   Which statement about $G$ is correct?

   [1 mark]

   • A$G$ is Eulerian, because every vertex has even degree
   • B$G$ is Eulerian, because it is connected and contains a cycle
   • C$G$ is neither Eulerian nor semi-Eulerian, because it has a vertex of degree $4$
   • D$G$ is semi-Eulerian, because exactly two vertices ($B$ and $D$) have odd degree

   (c)

   Write down a trail in $G$ that uses every edge exactly once.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A graph $H$ has vertices $P,\ Q,\ R,\ S,\ T,\ U$ and eight edges: $PQ$, $QR$, $RS$, $ST$, $TU$, $UP$, $PS$ and $QT$.

   (a)

   How many vertices of $H$ have odd degree?

   [1 mark]

   • A$2$
   • B$3$
   • C$4$
   • D$6$

   (b)

   Which of these is a Hamiltonian cycle of $H$?

   [1 mark]

   • A$P\to Q\to R\to S\to P$
   • B$P\to Q\to R\to S\to T\to U\to P$
   • C$P\to Q\to R\to S\to T\to U$
   • D$P\to Q\to T\to U\to P$

   (c)

   Explain why $H$ is neither Eulerian nor semi-Eulerian.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A connected simple graph $K$ has six vertices. Five of the vertices have degrees $2,\ 2,\ 3,\ 3$ and $4$, and the sixth vertex has degree $x$.

   (a)

   Show that $x$ is even, and state with a reason whether $K$ is Eulerian, semi-Eulerian or neither.

   [3 marks]

   (b)

   Given that $x=4$:
   (i) find the number of edges of $K$;
   (ii) a new graph $K'$ is formed by subdividing one edge of $K$ with a new vertex. State the number of vertices and the number of edges of $K'$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A park has six junctions $A,\ B,\ C,\ D,\ E$ and $F$ joined by seven paths: $AB$, $BC$, $CD$, $DE$, $EF$, $FA$ and $AD$.

   (a)

   (i) Show that there is a route that uses every path exactly once, and write one down.
   (ii) Explain why no such route can start and finish at the same junction, and suggest one extra path that would make this possible.

   [6 marks]

   (b)

   (i) Show that the graph is Hamiltonian.
   (ii) The junction $F$ 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.

   [6 marks]

   Total for question 4: 12 marks

End of questions