The Four-Color Problem

In 1852, a mathematician and England law student named Francis Guthrie, while coloring a map of the counties of England, observed that at least four colors were needed to guarantee that no two counties with a common border were colored the same. He conjectured that four colors were enough to color any map so that no two acjacent regions shared a color. Unable to prove the conjecture himself, he inquired of his former professor, the famous mathematician Augustus De Morgan, regarding the problem. De Morgan became interested in the problem, and began asking fellow mathematicians about it. The problem became known as the Four-Color Problem.

The problem went unsolved for many years. In 1879, Alfred Kempe published an alleged solution to the Four-Color problem that was widely accepted. Kempe's approach was to break the problem into a few different cases, then show each of these cases could be colored using only four colors. It wasn't until 1890 that another mathematician, Percy Heawood, discovered a flaw in Kempe's solution.

For many years, the Four-Color Problem grew in notoriety, and there were many attempted solutions and counterexamples to the conjecture, but all were flawed. Finally, in 1976, mathematicians Kenneth Appel and Wolfgang Haken proved the Four-Color Theorem. Their approach was in some ways similar to Kempe's: they broke the Four-Color Problem into different cases. But while Kempe only broke the problem into a few cases, Appel and Haken broken the problem into nearly 2,000 cases. In fact, there were so many cases to test, that Appel and Haken programmed a computer to do the job; it took the computer over a thousand hours to finish testing all the cases.

Many mathematicians were initially concerned about Appel and Haken's computer assisted solution. No major mathematical theorem had ever been solved with a computer before, and mathematicians weren't sure if they could trust the results. The solution was so long that it was impracticle for humans to check its validity by hand; how could they know that the computer had not malfunctioned or been programmed incorrectly? In time, other mathematicians were able to adapt Appel and Haken's methods to present simpler, more easily verifiable solutions to the Four-Color Problem. Today, most mathematicians accept Appel and Haken's solution as the first valid solution to the Four-Color Problem.