Combinatorics Planar graphs, embeddings, minors Theorem

Five colour theorem

Statement

Let $G$ be a finite planar graph. Then $\chi(G) \le 5$ .

Remarks

Proof idea: $G$ has a vertex $v$ of degree at most $5$ , by the edge bound for planar graphs. Colour $G - v$ by induction. If the neighbours of $v$ use all five colours, a swap of two colours along a Kempe chain frees one colour for $v$ . The four colour theorem is stronger, but its proof is much harder.

History

Percy John Heawood proved the theorem in 1890. He found an error in the 1879 proof of the four colour theorem by Alfred Kempe, and he used Kempe's ideas to prove five colours.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Graph colouring definition
Planar graph definition
K-colourable graph definition
Chromatic number definition
Five colour theorem statement

Tag	`06C0JBE52D`
URI	`m2://06C0JBE52D`
Kind	statement, theorem
Writing	W1 stated
MSC	05C15, 05C10
Status	This copy of the site has no build data. Run `m2 status 06C0JBE52D`.
Uses	Planar graph, Chromatic number
Same as	Wikidata Q105222412 Wikipedia Five color theorem

Five colour theorem

Statement

Remarks

History

Reading path

Further reading

What this page needs for W2

What links here