The Four-Color Problem

2015-04-21T20:40:56Z

Tbaldwin: Created page with "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 guar..."

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.

Grad Wiki - User contributions [en]

The Four-Color Problem