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.
Several conditions turn this mapmakers' conundrum into a well-defined mathematical problem.
A single shared point doesn't count as a shared border (above left). 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, unlike the map shown (above right); they can't have colonies scattered all over the map.
In addition, the unbounded area surrounding a cluster of countries and filling out the rest of the infinite sheet counts as a separate country that must also be colored.
The four-color problem fascinated and stumped professional and amateur mathematicians alike ever since it was first suggested in 1852 by Francis Guthrie, who had noticed he needed only four colors to fill in the counties on a map of England.
In a letter to his younger brother, Frederick, Guthrie asked whether it was true of any map. Frederick in turn described the problem to his mathematics instructor, Augustus De Morgan. The problem intrigued De Morgan, and he quickly appreciated that it wasn't quite as simple to solve as it appeared at first glance.
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 colour 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?"
Three colors are certainly not enough for every possible map. It's easy to come up with a simple map that requires four colors. In fact, Lewis Carroll (in his guise as mathematician Charles L. Dodgson) worked on the problem and figured out that four colors would be needed for the type of map shown below.
This map requires four different 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 (rules, above) was four or five.
To get a sense of how many colors are needed to color any map, you can experiment by drawing and coloring various configurations. It readily becomes apparent that the shape of the adjacent regions doesn't matter, but their arrangement does.
Here is one way to complete the map shown using four colors.
Indeed. when mathematicians work on the problem, they often draw graphs—networks of lines and points—to represent different configurations. That involves putting a a point (often called a vertex or node) at each country's capital and drawing a line (described as an edge) to connect the capitals of any pair of countries that has a common border.
Any map on the plane can be converted into a planar graph. In this example, involving a stylized map of the western United States, lines join points (nodes) within any two states that share a boundary.
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 U.S. map can be colored so that only two states require a fourth color. In this case, the two states are California and Ohio (shown shaded).
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. Not counting the water but including islands, Rhode Island has boundaries with three states—Massachusetts, Connecticut, and New York. In each case, a fourth color is always necessary to fill in the map.
Because Bolivia and Paraguay are surrounded by an odd number of countries, it takes four colors to complete a map of South America.
It is not at all obvious, however, whether a fifth color is needed for more complicated maps. It's not sufficient to show that you cannot have five countries that each shares a border with the other four. Even if a map contains no such set of countries, it might still require five colors. Mathematicians could prove, however, that no more than five colors are always sufficient to color any map.
The four-color problem defied solution for more than a century, despite years of map sketching, graph drawing, and logical argument.
In one such effort, Alfred Bray Kempe, a British lawyer and amateur mathematician, announced in 1879 that he had found a step-by-step map-coloring procedure guaranteeing that no more than four colors would be needed for any map.
Kempe's argument was convincing, but 11 years later, someone found a loophole. There were a few, special cases that his method did not cover.
In 1976, Kenneth Appel and Wolfgang Haken announced they had finally proved the four-color theorem. It was the kind of news that mathematicians would greet with champagne toasts. However, there was a shock awaiting anyone curious about how the four-color theorem had been conquered.
Hundreds of pages long, the proof was truly intimidating. 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 a readily verifiable conclusion.
The computer allowed Haken and Appel to analyze a large collection possible cases, a collection shown by mathematical analysis to be sufficient to prove the theorem.
The task took about 1,200 hours on one of the fastest computers available at the time; it would have taken practically forever by hand. It also meant the proof could not be verified without the aid of a computer. Furthermore, Appel and Haken had tried various strategies in computer experiments to perfect several ideas that were essential for the proof.
For a long time, some mathematicians remained 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 remarked in The Universe in a Handkerchief: Lewis Carroll's Mathematical Recreations, Games, Puzzles, and Word Plays.
Appel himself noted, "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."
In 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas presented a new proof of the four-color theorem. Robertson and his colleagues had started out to verify the Haken-Appel proof but soon gave up. They decided it would be more profitable to work out their own proof, following a somewhat streamlined version of the approach taken by Haken and Appel.
Instead of checking the 1,936 graphs (later cut to 1,476 configurations) required by the original proof, the team reduced the number to 633 special cases and proceeded from there. Still, the new proof contained computer steps that can't be verified by humans.
"However, from a practical point of view, the chance of a computer error that appears consistently in exactly the same way on all runs of our programs on all the computers under all the operating systems that our programs run on is infinitesimally small compared to the chance of human error during the same amount of case-checking," the mathematicians insisted.
"Apart from this hypothetical possibility of a computer consistently giving an incorrect answer, the rest of our proof can be verified in the same way as traditional mathematical proofs," they added.
Mathematicians have continued working on various other aspects of the map-coloring problem. They found, for example, that 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.
A map with intersecting straight lines as borders requires only two colors.
One question was 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 also 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.
As shown in this torus knitted by Carolyn Yackel, seven colors suffice.
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.
No comments:
Post a Comment