Edit made on January 03, 2015 by ColinWright at 17:06:42
Deleted text in red
/
Inserted text in green
WM
HEADERS_END
[[[> |>> IMG:AppelandHagan.jpg _ Appel and Hagan Haken <<| ]]]
The Four Colour Theorem is a problem from Graph Theory, and along
with the Bridges of Koenigsberg and the Three Utilities Problem is
one of the most common examples of Pure Mathematics found in school.
|>> [[[
Given any map, colour the regions _
so that regions sharing a border _
get different colours. _ _
How many colours do you need?
]]] <<|
The problem was first set in 1852. A false proof was given by Kempe (1879).
Kempe's proof was in fact accepted for a decade, but then Heawood showed an error using
a map with 18 faces. It wasn't until 1976 that a proof was finally given by
Kenneth Appel (standing) and Wolfgang Hagan Haken (seated) (1977). Even then there
was, and still is, some controversy, because the proof requires a computer to check a large number of sub-cases. These then have to be combined in a
clever way - the computer doesn't actually *do* the proof - but even so, it's
not a proof in the traditional sense.
It is interesting to compare the difficulty of the proof that four colours are sufficient
to colour any map on a sphere with the almost
trivial proof that seven colours are sufficient to colour any map
on a torus.
On the Klein Bottle and Mobius Band six colours are sufficient to colour any map on their surfaces.
* http://www.google.co.uk/search?q=four+colour+theorem
* http://en.wikipedia.org/wiki/Four_color_theorem