The Famous “Four-Color” Problem

The “Four-Color” problem sprang from a map, but is really about mathematics.

4-color Pacific NorthwestA Suggestion for Coloring a US Map (from Robin Thomas’s proof page)

Somewhere along the line the carto-enthusiast will hear of the famous tautology that, if you wish to color a map along the lines of the illustration (to differentiate different regions, as was popular in the old Hammond and Rand McNally world atlases of the mid-20th Century), you will need no more than four colors.

It’s a thought that’s lived at the back of our minds for a very long time. Recently we decided to track down the answer and whether or not the problem had, in fact, ever been solved. Parts of the answer were, we’ll be frank, a little over our heads–but fascinating none the less.

It Began With a Question

The whole sordid affair, legend has it, started in 1852 when South African botanist and mathematician Francis Guthrie (1831-1899), who was a student at University College London at the time, noticed that in coloring a map of Englands counties he only needed four colors to differentiate all the regions that bordered each other. His instructor, mathemeticia Augustus De Morgan (1806-1871) reported it thus:

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 – the following is the case in which four colours are wanted. Query cannot a necessity for five or more be invented…

From that beginning came what became known as the Four-Color Theorem, which can be succintly stated: “given any plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than four colors in such a way that no two adjacent regions receive the same color.” Regions can only be thought of as adjacent if they share an actual border segment, not merely touch at a point, moreover, the regions must be contiguous as well.

The Race Is On

Once released into the wild, the next thing to happen to any theorem is for it to be proven; in the same way that scientists attempt to reproduce the results of a notable new experiment, mathemeticians review the theorem and chase down any possible errors.

…quality of the proof rested upon confidence in the code used to render the proof

In fact, between the posing of the question and the turn of the 20th century, the theorem was proved no less than four times by four different mathemeticians, each eventually being shown as faulty through some thereto undiscovered flaw. It wasn’t until 1976 that the team of Kenneth Appel and Wolfgang Haken published a proof, but this required the use of a computer and was not universally acknowledged, in as much as the proof was so massive that human checking proved impractical, therefore the quality of the proof rested upon confidence in the code used to render the proof itself.

Latterly, more attempts to proof have been made. One of the more recent, a 1996 proof advanced by the team of Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas which was also computer-assisted, took a more efficient approach; by reducing the complexity of the problem the proof was more easily arrived at. This work built on the Apple and Haken work, addressing what were felt to be flaws in that proof.

The most recent proof was formalized in 2004 by Benjamin Werner and Georges Gonthier within a “proof assistant” computer application called Coq. This removes the need to trust the code that generated the solution; one must, however, decide how much confidence they have in Coq.

Strangely Enough…

In perhaps an ironic twist to our story, the famous “Four-Color” problem has really nothing much to do with practical cartography at all. Wikipedia’s overview seems to sum it up best of all:

According to Kenneth May, a mathematical historian who studied a sample of atlases in the Library of Congress, there is no tendency to minimise the number of colors used. Many maps use color for things other than political regions. Most maps use more than four colors, and when only four colors are used, usually the minimum number of colors actually needed is less than four.

There are also other considerations than mere regions on many maps: bodies of water (lakes and seas) can, depending on the map design, require yet another color. Overall, when choosing a color scheme for a map, many mapmakers’ concern is for balanced appearance, unless the object of the map is in fact to accentuate a certain feature or group of regions.

Indeed, in designing maps for print, the practical cartographer is probably not counting how many colors they’re using–or even limiting themselves to four.

Further Reading and References: