How few colors can be used on a map so no two adjacent countries have the same color?

This is an old problem, and it can be shown that you never need more than four colors to color a map drawn on a sheet of paper so that no two countries that share a border get the same color. It's quite famous in mathematics and is known as "The Four Color Theorem," but it's not at all easy to see why it would be true.

The idea dates to 1852 when Francis Guthrie was coloring a map of the counties of England and noticed he only needed four colors to do it. He asked his brother, who passed on the question to Augustus De Morgan, a famous mathematician, and from there it caught the imagination of a lot of great minds -- after all, the question is so easy to phrase, you'd think there would be a simple answer.

Various "proofs" appeared from time to time, but all were flawed until Kenneth Appel and Wolfgang Haken managed to nail it in 1976. Their proof actually triggered a lot of controversy in the mathematical community since it required the use of a computer. There's no easy way to understand the proof -- it involved reducing the possibly infinite number of maps to just 2,000 that needed to be checked explicitly, and that checking was done by a computer running for hundreds of hours.

Many people were unhappy with the result, worrying that the computer might have made a mistake, but the calculation has since been checked many times (and simplified a bit), and there is no doubt that it is correct. It is, however, fair to say that no human being really understands the result in the sense of being able to follow the whole proof with her or his brain.

Dr. Knowledge is written by physicists Stephen Reucroft and John Swain, both of Northeastern University. E-mail questions to drknowledge@globe.com or write Dr. Knowledge, c/o The Boston Globe, PO Box 55819, Boston, MA 02205-5819.