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

A Hamiltonian cycle is a cycle that passes through every vertex once and only once and returns to its start vertex. A graph with $n$ vertices needs a Hamiltonian cycle of exactly $n$ edges. Do not confuse it with an Eulerian cycle:

• Eulerian: uses every edge exactly once (vertices may be repeated).
• Hamiltonian: visits every vertex exactly once (some edges are left unused). A graph can be Eulerian, Hamiltonian, both or neither. A tree has no cycles at all, so it cannot have a Hamiltonian cycle. A graph with $n$ vertices and fewer than $n$ edges cannot have one.

A graph is planar if it can be drawn with no edges crossing. Deciding by trial and error can fail, so the planarity algorithm gives a systematic test for a graph that has a Hamiltonian cycle. Idea: draw the Hamiltonian cycle as a closed loop. Every other edge (a chord) joins two points on the loop, so it can be drawn either inside the loop or outside it. The graph is planar exactly when the chords can be shared between inside and outside with no crossings on either side.

1. Find a Hamiltonian cycle and draw it as a polygon.
2. List the edges not in the cycle (the chords).
3. Two chords conflict if their end points alternate around the cycle, so each chord separates the other's ends. Chords that share a vertex never conflict.
4. Put one chord inside. Any chord that conflicts with it must go outside. Continue placing chords so that conflicting chords are always on opposite sides.
5. If every chord can be placed, the graph is planar. If some chord conflicts with chords on both sides, the graph is non-planar. To test for a conflict between chord $XY$ and chord $UV$, check whether $U$ and $V$ lie on different arcs of the cycle between $X$ and $Y$.

Graph with Hamiltonian cycle $1-2-3-4-5-6-1$ and extra edges $13$, $24$, $15$, $46$. Conflicts: $13$ with $24$ (as $2$ is on one side of $13$ and $4$ on the other) and $15$ with $46$. No others. Place $13$ inside, so $24$ outside. Place $15$ inside, so $46$ outside. Inside, $13$ and $15$ share vertex $1$. Outside, $24$ and $46$ share vertex $4$. No crossings, so the graph is planar.

Cycle $A-B-C-D-E-A$, chords $AC$, $AD$, $BD$, $BE$, $CE$. Put $AC$ inside. $BD$ and $BE$ conflict with $AC$, so both go outside. $CE$ conflicts with $BD$, so it goes inside. Now $AD$ conflicts with $CE$ (inside) and $BE$ (outside), so it has no valid side. Hence $K_5$ is not planar. You may choose any valid starting chord. The final verdict is the same. The six-vertex graph made from a hexagon with its three long diagonals is also non-planar by the same method: all three diagonals conflict with each other, and three mutually conflicting chords cannot be shared between two sides.