Dr. Kenneth Appel and the Four Color Map Theorem: Part 1

Dr. Kenneth I. Appel died earlier this month at the age of 80. He is best known in mathematics four proving the Four Color Theorem, which states that any map of regions drawn on a flat piece of paper can be colored with no more than four colors in such a way that no two neighboring regions are the same color.

The proof was controversial in its day - the 1970s - because it used a computer to complete a vital but time consuming step.

Here is a map of the Western United States. Let me show a way to color it using four colors. It is not unique and the method I use causes a problem at the end, but by switching things around that problem can be solved.

An important idea in map coloring is that two regions are adjacent if they have a common edge, not if they meet at a common corner. In this example we have the four states that meet at a corner, In the same way a checkerboard can use two colors without people being confused, we can have Arizona and Colorado share a color, here signified by the number 1, and New Mexico and Utah share a different color, signified by the number 2.

Having done this, we now have states that border a 1 state and a 2 state, so I give all these states - Nevada, Wyoming and Oklahoma - the number 3.

Having done things in this method, I will now be forced to use a fourth color when mapping Kansas and Nebraska, and likewise there will be a forcing issue once, California, Oregon and Idaho are colored in. I also colored in Texas with a 1 since it was bordered by a 2 and 3.

I can easily finished the rest of the map, but this pattern has a problem. Imagine that some single region surrounds all these states. Because states on the outside edges have all four colors, this huge imagined state would have to be a fifth color, which would say four colors do not suffice. If I had started the problem knowing about that constraint, I could have still solved the new problem with four colors. The easiest way to do this changing as few states as possible is to switch the 3 and 4 in Wyoming and Nebraska, switch the 3 and 4 in Nevada and Oregon and change Washington to a 2. Then all the states on the outside have the numbers (colors) 1, 2 and 3 and the surrounding region can be given the color 4.

Tomorrow, I'll give a sketch of the proof, glossing over some difficult math and discussing the controversy of using computers in proofs.

I present this picture as tribute of the moment. Appel was at the University of Illinois when he published and the local post office commemorated his achievement with this postmark stating FOUR COLORS SUFFICE. It became a collector's item for mathematicians, like this postcard sent from the Urbana post office to Ulm, Germany while the postmark was being used.