Kuratowski's theoremAQA A-Level Further Maths: Revision notes

Section 1

Planar graphs

A graph is planar if it can be drawn in the plane with no edges crossing. A graph that is drawn with crossings can still be planar if a different drawing removes them: $K_4$ is planar (draw one vertex inside the triangle formed by the other three). Planarity is a property of the graph, not of one drawing. Two graphs are never planar: $K_5$ (5 vertices, 10 edges) and $K_{3,3}$ (6 vertices, 9 edges). Every attempt to draw them produces a crossing.

Key termsplanar graphnon-planar

Common mistake

Concluding a graph is non-planar because one drawing has crossings. You must show that every drawing does, which is what Kuratowski's theorem does.

Section 2

Subdivisions

To subdivide an edge, put a new vertex of degree 2 on it, replacing the edge $uv$ by the path $u,w,v$ . A graph obtained from another by repeated subdivision is a subdivision of it. Subdividing never changes planarity: a drawing of one gives a drawing of the other. To recognise a subdivision, suppress each vertex of degree 2 by replacing the path through it with a single edge. Example: $K_5$ with one edge subdivided has 6 vertices and 11 edges. It is still non-planar.

Key termssubdivisionsuppress

Exam tip

Count the edges of a subdivision: each new vertex adds exactly one edge, so a subdivision of $K_{3,3}$ with $k$ extra vertices has $9+k$ edges.

Section 3

Kuratowski's theorem

Kuratowski's theorem: a graph is non-planar if and only if it contains a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ .

$K_5$ : 5 vertices, each of degree 4, 10 edges.
$K_{3,3}$ : 6 vertices, each of degree 3, 9 edges. A subgraph is found by deleting vertices and edges, so the rest of the graph may contain extra vertices and edges that are simply ignored. 'If and only if' works both ways: containing such a subdivision proves non-planarity, and containing none proves planarity.

Key termsKuratowski's theoremsubgraph

Common mistake

Calling a graph non-planar because it looks similar to $K_5$ or $K_{3,3}$ . You must find the subdivision itself: every required pair of vertices joined by an edge or a path through degree-2 vertices.

Section 4

Proving a graph is non-planar

To show a graph is non-planar, find a subdivision of $K_5$ or $K_{3,3}$ inside it.

Look for five vertices of degree at least 4 (for $K_5$ ) or six vertices of degree at least 3 (for $K_{3,3}$ ).
Delete the other vertices and any extra edges.
Suppress vertices of degree 2 and identify the graph. Example: take vertices 1–7 with edges 12, 16, 17, 47, 23, 34, 36, 25, 45, 56. Vertex 7 has degree 2, so replace 1–7–4 by 14. With sets $\{1,3,5\}$ and $\{2,4,6\}$ all nine edges between the sets are present, giving $K_{3,3}$ . The graph is a subdivision of $K_{3,3}$ , so it is non-planar.

Key termsdegree-2 vertex

Exam tip

Check that every one of the nine $K_{3,3}$ pairs (or ten $K_5$ pairs) is joined, directly or through a path of degree-2 vertices. A missing pair means you have not found the subdivision.

Section 5

Proving a graph is planar, and quick tests

To show a graph is planar, draw it without crossings; or argue from Kuratowski's theorem that no subdivision exists. Useful counting facts:

A subdivision of $K_{3,3}$ needs at least 9 edges and 6 vertices; a subdivision of $K_5$ needs at least 10 edges and 5 vertices.
So any graph with 8 or fewer edges is planar, and any graph with 4 or fewer vertices is planar.
A graph with exactly 5 vertices is non-planar only if it is $K_5$ itself.
A subdivision of $K_5$ needs five vertices of degree at least 4, and one of $K_{3,3}$ needs six vertices of degree at least 3. Example: $K_5$ with one edge deleted has two vertices of degree 3, so it contains no subdivision of $K_5$ , and only 5 vertices, so none of $K_{3,3}$ . It is planar.

Key termsplanar drawing

Common mistake

Using edge count alone as a test: $K_{3,3}$ is non-planar with 9 edges, yet the octahedron is planar with 12.

That's the notes covered.

Carry on to the next subtopic.

Exam questions on Kuratowski's theorem

The complete graph $K_5$ has five vertices, each joined to every other vertex.
A new vertex $w$ is placed in the middle of one edge of $K_5$ , replacing that edge by two edges, to give a graph $H$ . State the number of edges of $H$ and explain whether $H$ is planar.2 marks
A graph $G$ has vertices $A,B,C,D,E,F$ and nine edges: $AB$ , $BC$ , $CD$ , $DE$ , $EF$ , $FA$ , $AD$ , $BE$ and $CF$ .
Use Kuratowski's theorem to decide whether $G$ is planar.2 marks
A graph $H$ has vertices 1 to 7 and ten edges: 1–2, 1–6, 1–7, 4–7, 2–3, 3–4, 3–6, 2–5, 4–5 and 5–6.
Show that $H$ is a subdivision of $K_{3,3}$ .3 marks

See the full worksheet

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).