Four Colors Suffice

In 1852, Francis Guthrie was coloring in a map of the counties of England. To ensure that the borders between counties were perceptible, his rule was never to fill in neighboring counties with the same color. To his surprise, Guthrie noticed that he only needed four colors to do this; no matter how complicated the configuration of English counties, a fifth colored pencil was never required to distinguish between neighbors.

Guthrie discussed his observation with his brother, a student of mathematics, who in turn asked his professor about it. But they could find nothing written about Guthrie's “four color theorem.” Somehow thousands of years of geometry and cartography had failed to notice the extremely simple fact that on a two-dimensional plane, no more than four shapes can all touch one another - the reason behind the theorem.

When I was 10 I heard tell of the four color theorem, and was occupied for several days with the task of disproving it. I created incredibly complicated arrangements of shapes: subdivided circles with moats around them, bridges over the moats, moats around the moats, etc. “This is it!” I would say of my latest drawing, before noticing the way in which the fifth color I had used could be obviated.

Mine was an impulse shared by many. In the 150+ years since Guthrie's observation, mathematicians have searched frantically for counter-examples to the four color theorem. None have stood up to scrutiny, but until very recently, neither had a satisfactory proof. It wasn't until 1976 that Kenneth Appel and Wolfgang Haken, with the help of a powerful computer, offered a proof of the theorem that has not since been disavowed.

Their proof asserts that any arrangement of shapes is geometrically equivalent to one of 1,936 arrangements (later reduced to 1,476). One thousand hours of computer processing proved that the four color theorem holds for those arrangements, and so it must hold in general.

Appel and Hankel's computer-based proof was so complex as to be considered impossible to check by hand. Though some mathematicians still have their doubts about it, the proof has nonetheless gained wide acceptance, and has been corroborated by several other computer-based methods.

However, a simple and elegant proof of the four color theorem eludes us. This creates a situation which is rather unique in mathematics: A bit of earnest doodling convinces anyone that the theorem is true, and yet centuries of searching by the best people around has yielded no straightforward explanation as to why.

Any ideas?