The planarity algorithm and Hamiltonian cyclesEdexcel A-Level Further Maths: Subtopic test

1. 1
   A graph has six vertices $A$, $B$, $C$, $D$, $E$ and $F$. Its edges are $AB$, $BC$, $CD$, $DE$, $EF$, $FA$, $AD$ and $BE$.

   (a)

   Which of the following is a Hamiltonian cycle in this graph?

   [1 mark]

   • A$A-B-C-D-A$
   • B$A-B-C-D-E-F-A$
   • C$A-B-C-D-E-F$
   • D$A-B-E-F-A$

   (b)

   The planarity algorithm is applied using the cycle $A-B-C-D-E-F-A$. Which statement is correct?

   [1 mark]

   • AThe graph is planar, with $AD$ and $BE$ both drawn inside the cycle
   • BThe graph is non-planar, because $AD$ and $BE$ conflict
   • CThe graph is planar, because it has a Hamiltonian cycle
   • DThe graph is planar, with $AD$ inside the cycle and $BE$ outside it

   (c)

   The edge $CF$ is added to the graph. Use the planarity algorithm to explain whether the new graph is planar.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A connected graph has six vertices and exactly five edges.

   (a)

   Which statement about this graph must be true?

   [1 mark]

   • AIt has a Hamiltonian cycle
   • BIt is Eulerian
   • CIt is a tree
   • DIt is a complete graph

   (b)

   A Hamiltonian cycle in a graph with six vertices contains exactly how many edges?

   [1 mark]

   • A$6$
   • B$5$
   • C$7$
   • D$12$

   (c)

   Explain why this graph does not have a Hamiltonian cycle.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Graph $H$ has vertices $1$, $2$, $3$, $4$, $5$, $6$ and edges $12$, $23$, $34$, $45$, $56$, $61$, $13$, $24$, $15$ and $46$. It contains the Hamiltonian cycle $1-2-3-4-5-6-1$. In the planarity algorithm, two edges that are not in the cycle conflict if they cannot both be drawn on the same side of the cycle without crossing.

   (a)

   List the edges of $H$ that are not in the cycle, and state which pairs of them conflict.

   [3 marks]

   (b)

   Hence use the planarity algorithm to show that $H$ is planar, stating which edges are drawn inside the cycle and which outside.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   The complete graph $K_5$ has vertices $A$, $B$, $C$, $D$, $E$ and contains the Hamiltonian cycle $A-B-C-D-E-A$. The graph $K_4$ is formed from the vertices $A$, $B$, $C$, $D$ of $K_5$ and the edges joining them.

   (a)

   Use the planarity algorithm to show that $K_5$ is not planar.

   [6 marks]

   (b)

   By considering $K_4$ and $K_5$, evaluate the claim that every Eulerian graph is planar.

   [6 marks]

   Total for question 4: 12 marks

End of questions