## Four Color Theorem Intro

We have all seen maps in which adjacent countries (or areas) are colored with different colors, so we can easily see the boundaries between them. Mathematicians asked, "Just how many colors are necessary?" They weren't trying to help out the map makers who occasionally bungle the job (I have seen several maps with mistakes in the coloring). The mathematicians found this an interesting, and diabolically difficult puzzle. Of course, the Four Color Theorem (previously called the Four Color Conjecture) was recently proven (by Wolfgang Haken and Kenneth Appel using a super computer at the University of Illinois, in 1976), showing that four colors is all you ever need, on a plane map. That proof is very long, and I will not show it. Instead, let's prove a "three color theorem:"

Three color theorem - More than three colors are required for some map or maps.

Proof: Look at the diagram, above left. Can't color it with just three colors, can you?

That was a little informal. But, that is essentially the proof. We wanted to show that three colors were not enough for some map. All we have to do is show a map that requires four colors, and we have proved our conjecture. I could have given some reasoning why you can't color this map with three colors. But it should be fairly obvious.

That first diagram is a very simple map. Doesn't it seem that there should be some complicated map that requires five colors? Mathematicians could never find one, no matter how complex. And now they have shown that there can be no map that requires five color. If you experiment with this, you will find maps which are extremely difficult to color with four colors. Some of the ways that you try will not work, they will require five or more colors. But there will always be a way to do it with only four colors.

In order to simplify their search for a proof, mathematicians use graphs instead of maps. And the Four Color Theorem becomes part of mathematical subject called Graph Theory. The map at the top of this article reduces to this graph, on the left. A graph is a set of points (vertices) and lines (edges). With a graph, we just need to specify that no two points connected by a line can be of the same color. The graph is confined to a plane, just like the map. And so, a fifth point cannot be connected to all four points of our graph.

Using graphs, it turns out that it is fairly easy to prove the Six Color Theorem, that at most six colors are needed to color a graph (and a map). Proving the Five Color Theorem is more difficult. Since the Three Color Theorem (above) is trivial (simple), the situation was that either four or five colors is the maximum number of colors needed. There was a Five Color Conjecture, that five colors were required for some graphs (and maps). This was disproved by the proof of the Four Color Theorem.

See The Bridges of Königsberg, for an introduction to graphs.

In order to approach a possible proof of the Four Color Theorem from other angles (as it were), mathematicians also examined similar theorems on other surfaces besides planes. The sphere and the torus (donut shape) were examined. It is surprisingly easy to show that seven (and no more than seven) colors are necessary on a torus. Any theorem for a sphere works for a plane, and vice versa.

The proof provided by Haken and Appel is considered ugly by most mathematicians, because it is so long and complicated, taking 1200 hours on a super computer. The proof took years to check for errors. The program had to check many specific graphs to see if five colors were necessary for any one of them. They had previously shown that all possible graphs could be reduced to those specific graphs.

See Four Color Theorem (summary of a new proof by N. Robertson, D. Sanders, and R. Thomas). Also see Nancy Casey - Four Color Theorem and The MacTutor History of Mathematics archive - four colour theorem.