Kuratowski's theorem

Kuratowski's theorem

Spec DA4 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A graph is planar if some drawing has no crossings; planarity belongs to the graph, not one drawing.
  • K5K_5 and K3,3K_{3,3} are never planar.
  • A subdivision inserts degree-2 vertices into edges and never changes planarity.
  • Kuratowski's theorem: a graph is non-planar if and only if it contains a subdivision of K5K_5 or K3,3K_{3,3}.
  • Any graph with 8 or fewer edges, or 4 or fewer vertices, is planar.

Planar graphs

A graph is planar if it can be drawn with no crossings, even if a particular drawing has some.

A planar graph can be drawn in the plane with no edges crossing. A drawing with crossings does not make a graph non-planar if a different drawing removes them: K4K_4 is planar, because one vertex can be drawn inside the triangle formed by the other three.

Two graphs are never planar: K5K_5 and K3,3K_{3,3}. Every attempt to draw them produces a crossing, so they are non-planar.

ABCD
K4K_4 drawn without crossings, one vertex inside a triangle.

Which of these graphs is non-planar?

Subdivisions

Subdividing an edge puts a new degree-2 vertex on it, which never changes whether the graph is planar.

To subdivide an edge, put a new vertex of degree 2 on it, replacing the edge uvuv by the path u,w,vu,w,v. A graph obtained by repeated subdivision is a subdivision of the original.

A drawing of one gives a drawing of the other, so planarity is unchanged. To recognise a subdivision, suppress each vertex of degree 2: replace the path through it with a single edge.

Example: K5K_5 with one edge subdivided has 6 vertices and 11 edges, and is still non-planar.

uvpwq
Subdividing edge uvuv adds vertex ww: one more vertex and one more edge.

K3,3K_{3,3} has one edge subdivided twice, adding 2 new vertices. How many edges does the new graph have?

Kuratowski's theorem

A graph is non-planar exactly when it contains a subgraph that is a subdivision of K5K_5 or K3,3K_{3,3}.

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

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.

K5K_5

Vertices:
5
Degree of each vertex:
4
Edges:
10

K3,3K_{3,3}

Vertices:
6
Degree of each vertex:
3
Edges:
9

A graph contains a subgraph that is a subdivision of K3,3K_{3,3}. What can you conclude?

Proving a graph is non-planar

Find a subdivision of K5K_5 or K3,3K_{3,3} inside it: pick candidate vertices, delete the rest, suppress degree-2 vertices and identify the graph.

To show a graph is non-planar, find a subdivision of K5K_5 or K3,3K_{3,3} inside it. Look for five vertices of degree at least 4, or six of degree at least 3.

Delete the other vertices and any extra edges, then suppress vertices of degree 2. If what remains is K5K_5 or K3,3K_{3,3}, you have the proof. Each degree-2 vertex is just a point along a subdivided edge.

  1. 1

    Find candidate vertices

    five of degree at least 4, or six of degree at least 3

  2. 2

    Delete the rest

    remove other vertices and extra edges

  3. 3

    Suppress and identify

    suppress degree-2 vertices and recognise the graph

Finding a Kuratowski subgraph

Worked example

A graph has vertices 1 to 7 and edges 12, 16, 17, 47, 23, 34, 36, 25, 45, 56. Show that it is non-planar.

What do you need to find to show a graph contains a subdivision of K3,3K_{3,3}?

Quick tests for planarity

To show a graph is planar, draw it without crossings; small graphs are planar automatically.

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

A subdivision of K3,3K_{3,3} needs at least 9 edges and 6 vertices; a subdivision of K5K_5 needs at least 10 edges and 5 vertices. So any graph with 8 or fewer edges, or 4 or fewer vertices, is planar. A graph with exactly 5 vertices is non-planar only if it is K5K_5 itself.

Example: K5K_5 with one edge deleted is planar.

Planar for certain

  • 4 or fewer vertices
  • 8 or fewer edges
  • Drawn with no crossings

Needed for non-planar

  • K5K_5 subdivision: 5 vertices of degree at least 4, 10 edges
  • K3,3K_{3,3} subdivision: 6 vertices of degree at least 3, 9 edges

A graph has 8 edges. Must it be planar?

Try an exam question

K3,3K_{3,3} has one edge subdivided once. State how many vertices and edges the new graph has, and whether it is planar. Give a reason.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

How many edges does K5K_5 have?

1 mark, marked against the mark scheme

Revision notes