Kuratowski's theorem
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.
- and 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 or .
- 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: is planar, because one vertex can be drawn inside the triangle formed by the other three.
Two graphs are never planar: and . Every attempt to draw them produces a crossing, so they are non-planar.
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 by the path . 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: with one edge subdivided has 6 vertices and 11 edges, and is still non-planar.
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 or .
Kuratowski's theorem: a graph is non-planar if and only if it contains a subgraph that is a subdivision of or .
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.
| Vertices | 5 | 6 |
|---|---|---|
| Degree of each vertex | 4 | 3 |
| Edges | 10 | 9 |
- Vertices:
- 5
- Degree of each vertex:
- 4
- Edges:
- 10
- Vertices:
- 6
- Degree of each vertex:
- 3
- Edges:
- 9
A graph contains a subgraph that is a subdivision of . What can you conclude?
Proving a graph is non-planar
Find a subdivision of or 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 or 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 or , you have the proof. Each degree-2 vertex is just a point along a subdivided edge.
- 1
Find candidate vertices
five of degree at least 4, or six of degree at least 3
- 2
Delete the rest
remove other vertices and extra edges
- 3
Suppress and identify
suppress degree-2 vertices and recognise the graph
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.
- 1
Vertex 7 has degree 2 (edges 17 and 47), so suppress it: replace 1–7–4 by the edge 14.
- 2
The edges are now 12, 14, 16, 23, 34, 36, 25, 45, 56: nine edges on six vertices.
- 3
Take the sets and . Every vertex of the first set is joined to every vertex of the second, and there are no edges within a set.
- 4
This is .
What do you need to find to show a graph contains a subdivision of ?
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 needs at least 9 edges and 6 vertices; a subdivision of 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 itself.
Example: 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
- subdivision: 5 vertices of degree at least 4, 10 edges
- subdivision: 6 vertices of degree at least 3, 9 edges
A graph has 8 edges. Must it be planar?
Try an exam question
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]
- [1]It has vertices and edges.
- [1]It is a subdivision of .
- [1]By Kuratowski's theorem it is non-planar.
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many edges does have?
1 mark, marked against the mark scheme
How many edges does have?
1 mark, marked against the mark scheme