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

What these 13 flashcards ask

Define a Hamiltonian cycle.
How many edges does a Hamiltonian cycle of a graph with n vertices have?
Eulerian cycle versus Hamiltonian cycle?
Can a tree have a Hamiltonian cycle?
What is a planar graph?
Which graphs does the planarity algorithm start from?
What is a chord in the planarity algorithm?
When do two chords conflict?
Do chords that share a vertex conflict?
Where must two conflicting chords be drawn?
When does the planarity algorithm show a graph is non-planar?
Is K4 planar? Is K5 planar?
What is a route that visits every vertex once but does not return to the start?

Exam questions on The planarity algorithm and Hamiltonian cycles

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
A connected graph has six vertices and exactly five edges.
Explain why this graph does not have a Hamiltonian cycle.2 marks
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

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).