This is a Clilstore unit. You can link all words to dictionaries.

THE FOUR COLOUR THEOREM

The four color theorem, or the four color map theorem, states that, given any separation of a plane into contigous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.

-map which can be face-coloured with exactly one colour.

A graph whose associated map can be face-colored with one color

-map which can be face-coloured with exactly two colours.

Map which has been face-colored with two colors

-map which can be face-coloured with three colours.

#-valent map which has been three-face-colored

-map which can be face-coloured with exactly four colours.

fancy circle sections colored

-map which can be coloured with four but can't be coloured with three colours.

europe colored

History of the problem

The Four Colour Conjecture was first stated just over 150 years ago, and finally proved conclusively in 1976.

The conjecture that any map could be coloured using only four colours first appeared in a letter from Augustus De Morgan (1806-1871) to his friend William Rowan Hamilton (1805-1865) the famous Irish mathematician in 1852. It had been suggested to De Morgan by one of his students, Frederik Guthrie.

Augustuc De Morgan (1807-1871) William Rowan Hamilton (1805-1865)

Augustus De Morgan (1807-1871) and William Rowan Hamilton (1805-1865)

The problem caught the imagination of many mathematicians at the time.
De Morgan used the fact that in a map with four regions, each touching the other three, one of them is completely enclosed by the others. Since he could not find a way of proving this, he used it as an axiom , the basis of his proof.

A Copy of De Morgan's Original Sketch A Simple Four Coloured Map

A copy of De Morgan's original sketch in his letter to Hamilton and a simple four colour map.

After collaborating with John Koch on the problem of reducibility, in 1976 at the University of Illinois, Kenneth Appel and Wolfgang Haken eventually reduced the testing problem to an unavoidable set with 1,936 configurations, and a complete solution to the Four Colour Conjecture was achieved. This problem of checking the reducibility of the maps one by one was double checked with different programs and different computers. Their proof showed that at least one map with the smallest possible number of regions requiring five colours cannot exist.

Graphs

If we place a vertex in the center of each region and then connect two vertices if their states share a border, we get a graph. Coloring regions on the map corresponds to coloring the vertices of the graph. Since neighboring regions cannot be colored the same, our graph cannot have vertices colored the same when those vertices are adjacent.

Simple Map and Dual Graph Colouring

The 3-coloured map on the left has 8 regions 10 vertices and 17 edges. Its dual graph on the right has 9 regions 9 vertices and 17 edges where the vertices are coloured the same as the areas of the map. The green vertex at the bottom of the graph represents the infinite external area for the map. Both the original map and its dual obey Euler's Formula for networks f+v−e=1 or, regions+vertices−edges=1. The duality relation is symmetric: the dual of the dual will be the original graph, where regions and vertices are exchanged.

Usage of the problem

Basically any Constraint Satisfaction Problem of degree four or higher are essentially the four-color theorem:

security camera placement optimization in a large building with many corners such that you minimize overlap
construction of a wildlife reserve (applying knowledge of food chains to see what combination of animals can live together and not completely wipe each other out)

Why is this problem so famous?

it took a lot of time to be solved
a lot of mathematicians tried solving it
it couldn't be solved without computer
a lot of mathematicians didn't accept the solution because it wasn't solved by a human being, but a machine