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

When mathematicians look at the four color map problem, they often turn the regions into vertices or nodes - here represented by ovals - and draw a line between any two nodes whose regions share a border. This object is called a graph, and because none of the lines connecting nodes crosses any other, the specific type of graph is called planar.

Dr. Kenneth Appel proved that all such planar graphs can be painted with four or less colors such that no two nodes that have a line connecting them directly are the same color. If you think about any graph, you could always add a new node an a few lines from that node to some of the other nodes on the existing graph. The implication of this is that there are infinitely many graphs.

Here's the tricky part of Dr. Appel's proof and I will not try to present an explanation for it.  There are ways to make one graph equivalent to another, which means that if one graph can be four-colored, the equivalent graph can be four-colored as well. Even though there are infinitely many graphs, Dr. Appel's method proved there are exactly 1,936 different equivalence classes.

It's not uncommon for mathematical proofs to have to several cases that have to be taken separately, but 1,936 is a lot of cases.  Instead of doing each one by hand, Appel decided to write a computer program that looked at every case. When it was finished and it had looked at all the data, it had proved each of the cases could be color with no more than four colors and the proof was complete.

There were many mathematicians who were not satisfied with the new method, but there were many who saw this as a way to use computers to forward the field of mathematical inquiry. While the controversy is not yet over, Appel's proof is accepted and the use of computers in math research is much more common now than it was in the 1970s.

Best wishes to the family and friends of Dr. Kenneth Appel, from a fan.

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.