The four-color map theorem states that, at most, four colors are needed to color any map, if two adjoining countries are always to be assigned different colors. The statement of the theorem is deceptively simple: it says that every imaginable map--regardless of how complicated the countries are and how many countries adjoin any given country--can be colored using only four colors. For the purposes of this problem, two countries are considered to adjoin each other if the boundary that they share has non-zero length, so that two countries that only meet each other in a corner can be given the same color (this fits in with commonsense principles of map-coloring, since there is no danger of confusion when two countries that only meet at a corner have the same color). So for example, a chessboard can be colored using only two colors, black and white.
Although the four-color theorem can be described in language that a child can understand, its proof is so difficult that more than one hundred years passed between the first statement of the problem and its successful proof. During that interval, many of the finest mathematicians worked on the problem, and one invalid proof was accepted as correct for more than a decade. The correct proof, discovered in 1976, was no less controversial, for it made unprecedented use of computers to do calculations that mathematicians could not check by hand. This brought into question the feasibility of examining the proof for errors, a key part of the acceptance of a proof by the mathematical community.
The first person to pose the map-coloring question appears to have been Francis Guthrie, a student at University College London. In 1852, Guthrie passed the question on through his brother to Augustus De Morgan, who immediately wrote to William Rowan Hamilton,
"A student of mine asked me today to give him a reason for a fact which I did not know was a fact--and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured--four colours may be wanted, but not more.... If you retort with some very simple case which makes me out a stupid animal, I think I must do as the Sphinx did...."
Hamilton's reply was quick and terse: "I am not likely to attempt your quaternion of colour very soon."
De Morgan continued to publicize the new problem, and soon it had attracted a good deal of attention. In 1879 Alfred Bray Kempe announced that he had proven the four-color theorem. His argument hinged on a method to color the countries one at a time, sometimes adjusting the color of previously colored countries to allow one of the colors to be used for a new country. Kempe's proof was hailed by the mathematical community, and Kempe was elected a fellow of the Royal Society. However, in 1890 Percy John Heawood found errors in the proof that Kempe was unable to correct, and the four-color theorem was returned to the status of conjecture.
In the decades that followed, mathematicians tried to shed light on the problem by relating it to the ideas of graph theory. A graph is a collection of points, called vertices, that are connected to each other by curves, called edges. A map can be turned into a graph by placing a vertex inside each country, and then connecting two vertices by an edge if the two countries share a boundary. A graph of this type will be a planar graph, that is, a graph whose edges never cross each other. The four color conjecture turns into the question, Is it possible to color each vertex of the graph using four colors, if two vertices that are connected by an edge are required to have different colors?
This translation of the problem, although elementary, transformed it from a problem about maps, which could have arbitrarily complicated boundary curves, to a question about graphs, which could be represented by a few points and edges. Mathematicians began to ask whether planar graphs could be put into a finite number of categories, so that each type of configuration could be analyzed to see if it was four-colorable.
In 1976 the mathematicians Kenneth Appel and Wolfgang Haken finally proved the four-color theorem, breaking down the different kinds of graphs into more than 1500 different configurations. Then, using a combination of ingenuity and computing power, they showed that each of those configurations could be colored with four colors. To perform the calculations, they used more than 1000 hours of computing time on three high-speed computers. Recently, the mathematicians Robertson, Sanders, Seymour, and Thomas have simplified the proof, which now relies on 633 configurations.
The reliance of the proof on computers made many mathematicians uneasy, although the proof is generally regarded as correct. The great mathematician Paul Erdös said, "I assume the proof is true. However, it's not beautiful. I'd prefer to see a proof that gives insight into why four colors are sufficient."
This is the complete article, containing 835 words
(approx. 3 pages at 300 words per page).
