10.1.3. Colouring of planar graphs
One of the most famous problem in graph theory is the four colour problem: prove that every plane graph is 4-colourable. The weaker assertion is almost immediate consequence of Euler's formula:
Theorem 10.5.: Every plane graph is 5-colourable.
Let us suppose that the assertion is false, and let G be 6-colourable plane graph with minimal number of vertices. Then G has a vertex x of degree at most 5.
Put .
Then H is 5-colourable,
say with colours 1,2,3,4,5.
Each of these colours must be used to colour at least one neighbour-hood of x, otherwise the missing colour could be used to colour x, and so G would be 5-colourable.
So, we may assume that , and we
denote the neighbours by
, and we colour
.

Suppose first that and
belong to
distinct components of
. Interchanging the colours 1 and 3 in the component of
we obtain
another colouring of H.



So, x is colourable with the colour 1, which is a contradiction.
So, we can suppose that and
belong to the
same component of
. Then, there is an
path
in H
whose vertices are coloured 1
and 3.




Is this possible?
The cycle of G
separates
from
but
cannot meet
this cycle.
So, G is not a planar graph, which contradicts our assumption.
Let .
The consequence of the 5-colour
theorem: .
-
The original form of the four colour problem was posed by: Francis Guthrie in 1852: show that every plane map can be coloured with four colours.
-
His teacher, de Morgan, circulated the problem among his colleagues, but the problem was first made popular in 1878 by Caley, who mentioned it before the Royal Society.
-
The first ″proofs″ were given by Kempe (1879) and Tait (1880).
-
Heawood's refutation of Kempe's proof was published in 1891. He modified the proof to obtain the five colour problem.
-
Petersen in 1890 proved that Kempe's proof contained false assumptions: He proved that the four colour problem is equivalent to the conjecture that every cubic graph has edge chromatic number three.
-
Birkhoff's introduction of the chromatic polynomial at the beginning of the 20. century contributed to the solution.
-
During the 20. century a lot of works were made by various authors giving lower bounds on the order of a possible counterexample.
-
In 1943 Hadwiger made a deep conjecture containing the four colour problem as a special case: if
then G is contractible to
.
-
The problem was at last solved by Appel and Haken in 1976 using fast electronic computer and considering more than 1900 reducible configurations to complete the proof.