Four Colors Suffice

I have been fascinated by the map coloring problem since I was first introduced to it in the amazing One Two Three... Infinity by George Gamow, quite possibly the most influential single book that I read as a child. I'd heard a while back that it was finally solved (some time after One Two Three... Infinity was written), but I wasn't familiar with the story, which turns out to be intriguing in several respects.

Stated briefly, the map coloring problem is this: assuming that each country on the map is contiguous (no countries broken into several parts that are unconnected or only connected at a single point), how many colors does it take in the worst case to color a map so that no country has the same color as another with which it shares a border? Any number of countries can meet at a single point and still be colored the same color, but no two countries with a common border can have the same color.

It's fairly trivial to see that at least four colors are required. Consider, for instance, a small country surrounded by a ring of three other countries. All countries share at least one border with each other country in the map, and therefore they must all be colored a different color. I also found it easy to convince myself that it's reasonable for no more than four colors to be required, but this has been amazingly difficult to prove.

Like Fermat's Last Theorem, the map coloring problem had the advantage of being a long-standing unsolved problem in mathematics (if less important and more obscure to mathematicians) that was trivial to explain even to someone not familiar with math. I think this is why it's attracted so much attention. Wilson traces the history and work on the problem from its believed origins in 1852 through the "proof" finally arrived at in 1976 and the controversy that followed. Appel and Haken proved that only four colors were required for any map using an incredibly complex process and argument, of which substantial portions were proven by computer. This was very unlike the sort of proof that mathematics was used to, and while nearly everyone accepts the result, it remains an interesting open question whether their method truly constitutes a proof in the mathematical sense rather than something weaker. It also begs the question of why only four colors are required; to this day, there is no deeper explanation in terms of underlying principles of why four colors are enough. It just appears to be true.

Four Colors Suffice is a fairly comprehensive look at the problem, covering many of the approaches and secondary results reached over the years. As such, parts of it are heavy going unless you're really interested in the mathematics and reasoning, and it can occasionally get bogged down. It is, however, the best treatment of the topic that I've seen, and it doesn't require a comprehensive understanding of advanced mathematical topics. Anyone with a basic familiarity with mathematics and a good grasp of logic should be able to follow this book.

The worst flaw of the book is, annoyingly, the typography. For some reason, the publishers chose to use a sans serif font for the regular text and a serif font for quotations, and also chose not to indent quotations at all. This is so opposite of how books are normally typeset that I was constantly getting confused over whether I was reading Wilson's words or a quote from someone else. It was very distracting, and I recommend trying to find a different edition if you can; hopefully not all of them make this mistake.

I'm not sure there's quite enough material to sustain a book this size for the curious non-mathematician, and Four Colors Suffice did drag in places. I'm not sure it would be of as much interest to someone less interested in the problem; the surrounding history is interesting and touches on the politics of math in places, but it's not particularly world-shaking stuff. Still, it satisfied my curiosity on something I'd been wondering about for years, and was well worth reading for that.

Rating: 6 out of 10

Reviewed: 2005-05-03