19/05/2024
Four-colour map problem
➖➖➖➖➖➖➖➖➖➖➖
Can you create a map where four colours are not enough to colour its region?
The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. This problem is sometimes also called Guthrie's problem after F. Guthrie, who first conjectured the theorem in 1852. The conjecture was then communicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on the conjecture.
Fallacious proofs were given independently by Kempe (1879) and Tait (1880). Kempe's proof was accepted for a decade until Heawood showed an error using a map with 18 faces (although a map with nine faces suffices to show the fallacy). The Heawood conjecture provided a very general assertion for map coloring, showing that in a genus 0 space (including the sphere or plane), four colors suffice. Ringel and Youngs (1968) proved that for genus , the upper bound provided by the Heawood conjecture also give the necessary number of colors, with the exception of the Klein bottle (for which the Heawood formula gives seven, but the correct bound is six).