Math 2.0

Combinatorics Planar graphs, embeddings, minors Theorem

Four colour theorem

Builds on Planar graphChromatic number

Statement

Let GG be a finite loopless planar graph. Then χ(G)≤4\chi(G) \le 4.

Remarks

In terms of maps: four colours are enough for the regions of a map in the plane. Regions with a common boundary segment get different colours. The bound is sharp, because K4K_4 is planar and χ(K4)=4\chi(K_4) = 4.

History

Francis Guthrie stated the problem in 1852. Kenneth Appel and Wolfgang Haken proved the theorem in 1976, with the help of a computer. Robertson, Sanders, Seymour and Thomas gave a simpler proof in 1997. Georges Gonthier and Benjamin Werner checked a proof in the Coq proof assistant in 2005.

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
Graph colouring, definition, no evidence levelGraph colouringdefinitionPlanar graph, definition, no evidence levelPlanar graphdefinitionK-colourable graph, definition, no evidence levelK-colourable graphdefinitionChromatic number, definition, no evidence levelChromatic numberdefinitionFour colour theorem, statement, no evidence levelFour colour theoremstatement
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
  1. Graph colouring definition
  2. Planar graph definition
  3. K-colourable graph definition
  4. Chromatic number definition
  5. Four colour theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Four_color_theorem, Formulation
About this page
Tag0M406JC8J1
URIm2://0M406JC8J1
Kindstatement, theorem
WritingW1 stated
MSC05C15, 05C10
StatusThis copy of the site has no build data. Run m2 status 0M406JC8J1.
UsesPlanar graph, Chromatic number
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.