The planarity algorithm and Hamiltonian cyclesEdexcel A-Level Further Maths: Mind map

Exam questions on The planarity algorithm and Hamiltonian cycles

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$.
   The edge $CF$ is added to the graph. Use the planarity algorithm to explain whether the new graph is planar.2 marks
2. A connected graph has six vertices and exactly five edges.
   Explain why this graph does not have a Hamiltonian cycle.2 marks
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.
   List the edges of $H$ that are not in the cycle, and state which pairs of them conflict.3 marks