Four Color Map Theorem Creates New Branch of Mathematics: Graph Theory

Francis Guthrie, a 21 year old mathematics student at University College in London, was mapping the counties of England in 1852 when he noticed that he only needed four colors for the map. 

Francis asked his younger brother, Frederick Guthrie, if this was true for any map. Frederick took the problem to his professor, Augustus de Morgan. In 1878 Arthur Cayley presented this problem to the London Mathematical Society. 

Cayley and various others tried to prove it over the next century. In 1879 and 1880, Alfred Kempe and Peter Tait found a proof for the Four Color Map Theorem. In 1890 and 1891, mathematicians Percy Heawood and Julius Petersen showed that both Kempe and Tait's proofs were wrong.

In 1976 Wolfgang Haker and Kenneth Appel of the University of Illinois proved the theorem using a computer. It took them four years to write the computer program for the Cray computer, which took 1200 hours to check 1476 configurations. Some mathematicians are troubled by the proof by computer. They feel that a theorem so easy to understand should be able to be proved by hand. 

In 1997,N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas improved Appel and Haken’s methods to reduce the number of cases (but still rely on computer assistance). In 2005, Georges Gonthier publishes a “formal proof” (automating not just the case-checking, but the proof process itself ).

Anyone who can prove the theorem without the computer may win the Fields Medal, the math equivalent of the Nobel Peace Prize. 

Definition: A k-coloring of a map is an assignment of k colors, one to each country, in such a way that no two countries sharing a border have the same color. A map is k-colorable if it has a coloring with at most k colors.

During class, I first built maps in two colors, then building on those, three colors, then four, then five. I presented this solution as a failed map since you should never need more than four colors according to Guthrie. We then rebuilt that same map to show them that it could be done in four colors.

I had them start with Australia with six countries and challenged them to do this in three colors only. Then they could see the western United States would require four colors. Next, they struggled with three difficult maps that were solvable if you started with the region with the most adjacencies. This is similar to a complicated move in chess where you have to plan ahead instead of just making an impulsive move. Some of our best Mathletes got stuck on these; however, many were able to fix their mistakes to solve them. 

The next challenge is almost impossible to do without serious concentration. On April 1, 1975, Martin Gardner, editor for many years of the Mathematical Games column in Scientific American, published a map with a claim that it required five colors if adjacent countries were to receive distinct colors. This was just a hoax, as it is solvable but very hard. For an extra challenge consider the exterior "ocean" as an additional country and assign it one of the four colors too.

Now, color in the maps of the United States, Massachusetts, and each continent with no more than four colors. Remember no color can touch another color on a side, but may meet at a point.

In order to prove the Four Color Map Theorem, an entire new type of mathematics was created, called Graph Theory. This has applications in computer science, linguistics, physics and chemistry, biology, social sciences, and geometry.