| | Ivars Peterson's MathTrek |
January 6, 1997
The question is whether four colors are always enough to fill in every conceivable map that can be drawn on a flat piece of paper so that no countries sharing a common boundary are the same color. A single shared point doesn't count as a shared border. Otherwise, a map whose countries are arranged like the wedges of a pie would need as many colors as there are countries. Also, countries must be connected regions; they can't have colonies scattered all over the map.
The four-color problem has intrigued and stumped professional and amateur mathematicians alike ever since it was first proposed in 1852 by a British graduate student, Francis Guthrie, in a letter to his younger brother.
Toward the end of the nineteenth century, Lewis Carroll turned the map-coloring problem into a kind of game. A passage in one of his manuscripts gives the rules:
"A is to draw a fictitious map divided into counties.
B is to color it (or rather mark the counties with names of colours) using as few colours as possible.
Two adjacent counties must have different colours.
A's object is to force B to use as many colours as possible. How many can he force B to use?"
It's easy to come up with a simple map that requires four colors. It's not at all obvious, however, whether a fifth color is needed for more complicated maps. Because the conjecture that four colors suffice hadn't yet been proved, Carroll didn't know with certainty whether the answer to his question was four or five.
 This map requires four different colors. |
To get a sense of how many colors are necessary to color any map, one can experiment by drawing and coloring in various configurations. It readily becomes apparent that the arrangement of the adjacent regions does matter, but their shape does not. Indeed, when mathematicians work on the problem, they draw graphs -- networks of lines and points -- to represent different configurations. That involves putting a vertex at each country's capital and drawing a line (or edge) to connect the capitals of any pair of countries that has a common border. Four colors turn out to be necessary in any situation in which a region has common borders with an odd number of neighboring regions. A map showing the states of the United States features several such instances. For example, Nevada has borders with five states, and Kentucky with seven. If you don't count the water and include islands, Rhode Island has boundaries with three states: Massachusetts, Connecticut, and New York. In each case, a fourth color is always necessary to complete the map. |
The proof was intimidating, strewn with diagrams and hundreds of pages long. Even more dismaying to many mathematicians was that, for the first time, a computer had been used as a sophisticated accountant to enumerate and verify a large number of facts needed for the proof. There was no simple, direct line of argument leading to an easily verifiable conclusion.
Some mathematicians remain unsatisfied with this state of affairs. "Even if the theorem is true, as it almost certainly is, it still awaits a simple proof that does not require hours of computer time," Martin Gardner remarks in The Universe in a Handkerchief.
Appel, who is now at the University of New Hampshire, has said, "It has troubled our profession that a problem that can be understood by a school child has yet to be solved in a way that better illuminates the reason that only four colors are needed for planar maps."
Map-coloring didn't end with the proof of Appel and Haken. Mathematicians have continued working on various aspects of the problem. For example, not every map drawn on a surface requires the full complement of colors. A map consisting of just one country requires, of course, only one color. The four-color theorem merely sets an upper bound. The question is whether there exists a quick, efficient way to tell whether a given map requires the full complement of colors.
For maps on a flat surface, the answer appears to be "no." For maps on a surface shaped like a doughnut (torus), a double torus, and similar shapes, however, the answer is "yes." Mathematicians proved some time ago that any map drawn on a torus requires at most seven colors, on a double torus, eight colors, and so on.
Recently, Carsten Thomassen, a graph theorist at the Technical University of Denmark, demonstrated that each type of surface (other than the plane) has a finite list of maps that require six colors. On the torus, there are only four such maps. Any map on a torus that doesn't contain one of these as a submap can be colored with just five crayons.
Thomassen has so far identified the complete list of critical submaps only for the torus. It may prove quite difficult to compile such lists for more complicated surfaces. Nonetheless, it can be done in principle.
It's nice to see there's still life in the old problem of coloring a map. The search for a simple, incisive proof of the four color theorem goes on, suggesting new puzzles and leading to novel mathematical techniques that turn out to be useful in applied mathematics and computer science.
Copyright © 1996 by Ivars Peterson.
______. 1977. The solution of the four-color-map problem. Scientific American 237(October):108-121.
Cipra, Barry A. 1996. Advances in map coloring: Complexity and simplicity. SIAM News (December):20.
Gardner, Martin. 1996. The Universe in a Handkerchief: Lewis Carroll's Mathematical Recreations, Games, Puzzles, and Word Plays. New York: Copernicus.
______. 1995. New Mathematical Diversions. Washington, D.C.: Mathematical Association of America.
Olivastro, Dominic. 1992. Color proof. The Sciences (May/June):53-55.
Peterson, Ivars. 1988. The Mathematical Tourist: Snapshots of Modern Mathematics. New York: W.H. Freeman.