Abstract
M.Sc.
Within the field of Graph Theory the many ways in which graphs can be coloured
have received a lot of attention over the years. T.R. Jensen and B. Toft provided a
summary in [8] of the most important results and research done in this field. These
results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is
attempted to colour every map with four colours in such a way that adjacent countries
will be assigned different colours. This was first noted as a problem by Francis
Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical
Society. In 1879 Kempe published a proof, but it was incorrect and lead
to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977
Appel and Haken were the first to publish a solution for the four colour problem in
[2] of which the proof was mostly based on work done by Birkhoff and Heesch. The
proof is done in two steps that can be described as follows: firstly it is shown that
every triangulation contains at least one of 1482 certain “unavoidable configurations”
and secondly, by using a computer, it is shown that each of these configurations is
“reducible”. In this context the term “reducible” is used in the sense that any plane
triangulation containing such a configuration is 4-colourable by piecing together 4-
colourings of smaller plane triangulations. These two steps resulted in an inductive
proof that all plane triangulations and therefore all planar graphs are 4-colourable.