The planarity algorithm and Hamiltonian cycles

The planarity algorithm and Hamiltonian cycles

Spec 1.4 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A Hamiltonian cycle visits every vertex exactly once and returns to the start, using exactly nn edges.
  • Eulerian uses every edge once; Hamiltonian visits every vertex once.
  • The planarity algorithm draws a Hamiltonian cycle as a polygon, then places the other edges (chords) inside or outside.
  • Chords conflict if their end points alternate around the cycle; chords sharing a vertex never conflict.
  • Planar if every chord can be placed with conflicting chords on opposite sides; otherwise non-planar.

Hamiltonian cycles

A cycle through every vertex exactly once, returning to its start: it has exactly nn edges for nn vertices.

A Hamiltonian cycle passes through every vertex once and only once and returns to its start vertex. A graph with nn vertices needs a Hamiltonian cycle of exactly nn edges. A tree has no cycles, so it cannot have one.

To find one, write down the vertices of degree 2 first: both of their edges must be in the cycle. A route that does not return to the start is a Hamiltonian path, not a cycle.

123456
Hamiltonian cycle 1-2-3-4-5-6-1: every vertex once, back to the start.

Eulerian cycle

  • Uses every edge once
  • Vertices may repeat

Hamiltonian cycle

  • Visits every vertex once
  • Some edges may be unused

A graph has 88 vertices. How many edges does a Hamiltonian cycle in it have?

The idea of the algorithm

Draw the Hamiltonian cycle as a loop; every other edge is a chord drawn inside or outside it.

A graph is planar if it can be drawn with no edges crossing. Trial and error can fail, so the planarity algorithm gives a systematic test for a graph that has a Hamiltonian cycle.

Draw the Hamiltonian cycle as a closed loop. Every other edge (a chord) joins two points on the loop, so it can be drawn inside or outside. The graph is planar exactly when the chords can be shared between inside and outside with no crossings on either side.

123456
Chords 13 and 24 conflict: drawn on the same side of the cycle they cross.

In the planarity algorithm, what is a chord?

The algorithm step by step

List the chords, find which conflict, then place conflicting chords on opposite sides.

Two chords conflict if their end points alternate around the cycle, so each separates the other's ends. Chords that share a vertex never conflict. To test chords XYXY and UVUV, check whether UU and VV lie on different arcs of the cycle between XX and YY.

Put one chord inside; any chord that conflicts with it goes outside. If some chord conflicts with chords on both sides, the graph is non-planar. List the conflicting pairs before placing anything.

  1. 1

    Draw the cycle

    find a Hamiltonian cycle and draw it as a polygon

  2. 2

    List the chords

    all edges not in the cycle

  3. 3

    Find conflicts

    chords whose end points alternate around the cycle

  4. 4

    Place chords

    put conflicting chords on opposite sides

  5. 5

    Decide

    all placed means planar; a chord with no valid side means non-planar

The planarity algorithm

The cycle is 1-2-3-4-5-6-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1. Do the chords 1414 and 2525 conflict?

A planar example

Every chord can be placed: conflicting chords go on opposite sides and the rest share sides.

A graph has Hamiltonian cycle 1−2−3−4−5−6−11-2-3-4-5-6-1 and extra edges 1313, 2424, 1515, 4646. The only conflicts are 1313 with 2424 and 1515 with 4646.

123456
The graph drawn without crossings: chords 13 and 15 inside the cycle (solid), chords 24 and 46 outside it (dashed).

Inside the cycle

  • 13
  • 15

Outside the cycle

  • 24
  • 46

Worked example

Use the planarity algorithm to decide whether the graph is planar.

In this example, why can 1313 and 1515 both be drawn inside?

A non-planar example

A chord that conflicts with chords on both sides has no valid place, so the graph is non-planar.

Take K5K_5 with cycle A−B−C−D−E−AA-B-C-D-E-A and chords ACAC, ADAD, BDBD, BEBE, CECE. You may choose any valid starting chord: the 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.

ABCDE
K₅: the pentagon A-B-C-D-E-A is the cycle; the diagonals are chords.

Worked example

Use the planarity algorithm on K5K_5.

Why does the algorithm show that K5K_5 is non-planar?

Try an exam question

A graph has Hamiltonian cycle 1−2−3−4−5−6−11-2-3-4-5-6-1 and three further edges 1414, 2525 and 3636. Use the planarity algorithm to show that the graph is not planar.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

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

1 mark, marked against the mark scheme

Revision notes