BOOKS: Four Colors Suffice, Robin Wilson (2002)

Wilson gives us a history of the four-color problem and its solution. At the opening, he states the problem very simply: Can every map be colored with at most four colors in such a way that neighboring countries are colored differently?

In itself, it's not a really important question -- it's not as if mapmakers are required to limit themselves to the fewest possible colors -- but it did lead to new ideas that had important implications in other areas of mathematics. The field known as graph theory, in fact, developed almost entirely out of ideas generated in the search for a solution to the four-color problem.

The problem appears to have first been posed by Augustus De Morgan, a British mathematics professor, in 1852, and it would not be solved until 1977, when the team of Kenneth Appel, Wolfgang Haken, and John Koch would publish their proof.

That proof itself turned out to be controversial in its own right. It was, in essence, a more complicated version of the following 3-line mini-proof:

1. Every map has either feature A or feature B (a map may have both, but every map has at least one.)
2. Four colors suffice to color any map with feature A.
3. Four colors suffice to color any map with feature B.

Obviously, if you can prove all three of those statements, you've solved the problem, and this was the approach taken by Appel, Haken, and Koch. The big difference is that instead of "feature A or feature B," their unavoidable set of configurations contained almost 1500 different features, and a "four colors suffice" proof was required for each one.

To generate that many proofs took nearly 1200 hours of computer time, and the resulting overall proof was a four-foot stack of computer paper; it was impossible for any mathematician to thoroughly check all of those subproofs. This raised the question of whether a computer-generated proof could even be called a proof, and even if it could, some were unsatisfied by it on aesthetic grounds. Daniel Cohen, another mathematician who had worked on the problem, argued that "the real thrill of mathematics is to show that as a feat of pure reasoning in can be understood why four colors suffice. Admitting the computer shenanigans of Appel and Haken to the ranks of mathematics would only leave us intellectually unfulfilled."

A somewhat simpler proof would eventually be produced by another team of mathematicians, with an unavoidable set of only 633 configurations to be proven as opposed to the original proof's 1,482, but the approach was the same, and the new proof was still computer generated.

There were a lot of false steps and failed attempts in the 125 years between the initial statement of the problem and its solution, and Wilson's history is an entertaining one. It is not for the mathematical novice, as the theory does occasionally get a bit dense. I found that I could almost always skim through the worst of it, though, and at the end of the section, I would at least understand what had just been proven and why it was important, even if I didn't quite follow all the details of how it had been proven.