Whirlwind Tour
of Math

Fall 2007
course
navigation

Coloring Maps

Sometimes an innocuous non-mathematical question is the start of a epic mathematical journey. One such journey started in 1852. We have a map of the world and wish to color it in such a way that any two neighbouring countries have different colors. How many different crayons so we need? What if the countries were arranged differently than they are now? Some experimentation suggests that the answer is probably four, however the countries are arranged (we need some technical conditions like contiguity of countries before we can precisely formulate the question).
Kempe believed he had a proof towards the end of the 19th century, and was elected to the Royal Society partly on this basis. Ten years later a mistake was found. It took until 1976 for the answer to be confirmed as four and the proof was a huge affair, involving the significant use of computers for the first time in a major mathematical result. This left the math community divided as to whether this was really a proof. No human has ever read the whole thing and checked the details. More unsettling for many is that the proof gives very little indication why the answer is four.
If we take on this topic we'll prove that five colors are always sufficient (this result was salvaged from Kempe's work) and investigate some generalisations (What if we lived on a torus? What if each country had a colony on the moon that had to be colored with the same color as the country?) Along the way we'll solve a seemingly unrelated question: What "regular" (aka Platonic) solid shapes exist? (Regular means that each face is the same and all the angles are the same---the cube is an example.)
http://cs.marlboro.edu/ courses/ fall2007/math_tour/ Coloring_Maps
last modified Monday October 1 2007 9:27 am EDT