In 1852, Francis Guthrie (pictured above), a British mathematician and botanist was looking at maps of the counties in England and discovered that he could always color these maps such that no adjacent country is the same color with *at most* four colors. Would this work for any map?

Here is a map of the US colored with four colors. Notice that no two adjacent states have the same color.

Here is an early map of the US colored with four colors. Again, notice that no two adjacent state have the same color.

Here is a map of the counties in New York state colored with four colors.

Here is a map of the parts of Liechtenstein colored with four colors.

This problem was a curiosity for some time but in 1879 A. Kempe claimed to have solved the problem – and even published his solution! Unfortunately in 1890 the Four Color Theorem was demoted to the Four Color Conjecture since P. Heawood found an error in Kempe’s proof. Heawood was not able to show that there was a map that could be colored (with no two adjacent countries having the same colors) with no fewer than 5 colors. But he did show that Kempe’s argument was flawed.

This is an important distinction to make here. In mathematics if somebody makes a claim, like “four colors suffice”, if you want to prove them wrong, you would need to produce a counterexample – a map that needs a minimum of five colors. This is different from pointing out a flaw in their argument – as Heawood did to Kempe. All you can say here is that their *proof* is wrong but the *result*, “four colors suffice”, could still be true.

Back to our story. Heawood spent the rest of his like trying, unsuccessfully, to solve the Four Color Conjecture. Others who followed him were able to show that if you place a limit on the number of countries on your map, then four colors suffice. For example, Franklin in 1922 proved that four colors suffice for any map with at most 25 countries. Reynolds, in 1926, proved that four colors suffice for maps with at most 27 countries, Winn to 35 in 1940, Ore and Stemple to 39 in 1970 and Mayer to 95 in 1976.

The problem was eventually solved by Appel and Haken in 1976 when the announced that “four colors suffice”. There is some controversy about this since their solution involves making reductions to the problem to certain cases and then using a massive computer program to check these cases. Some argue that this solution does not really count as a solution since it can’t really be checked. How to we know the program was done correctly? Others argued that this problem is a *mathematics* problem and should have a *mathematical* solution – not a computer one. Others argue that the Appel and Haken solution is just fine. You, as a student, are most welcome to enter the debate.

By the way, Appel and Haken were from the University of Illinois and after their discovery, the university added a “four colors suffice” to their outgoing mail postage cancellation.

To give you a bit of the flavor of what goes into proving map coloring problems, let us prove “six colors suffice”

**Theorem A:** *Every map can be colored with at most six colors.*

Before starting here not that the use of “at most”. There are certainly maps which can be colored with fewer colors.

As a warm up exercise we will prove a weaker version of this theorem.We will say that a map is *standard* if exactly three edges meet at each vertex. Here is an example of a standard map.

Here is another standard map.

Here is a non-standard map. Note how the middle vertex meets six edges.

**Theorem B:** *Every standard map can be colored with at most six colors.*

Before doing this, we need a technical lemma.

**Lemma:** *Every standard map has at least one country (face) with five or fewer edges.*

**Proof:** We will prove this by contradiction. Suppose the conclusion of the lemma is false. Then every face has *at least* 6 edges. If v is the number of vertices, e is the number of faces, and f is the number of faces, notice that 6 f ≤ 2 e (each face generates at least six vertices but each vertex gets counted twice). Also notice that since we have a standard map we have 3 v = 2 e (each vertex generated exactly three edges but each edge gets counted twice). Euler’s formula says that 1 = v – e + f. But v = 2/3 e and f ≤ 1/3 e and so v – e + f ≤ 2/3 e – e + 1/3 e = 0. Thus we conclude that 1 ≤ 0 which is clearly false. So it must be the case that there at least one face with five or fewer edges. **QED.**

**Proof of Theorem B.** We will use the principle of mathematical induction (I’ll go into this in great detail in class). Suppose that every map with n faces can be colored with at most six colors. We now need to show that every map with n + 1 faces can be colored with at most six faces. By the lemma, there is a face with five or fewer edges. Here is a representative picture

Remove that face and you will have a map with n faces. Remember that you started with a map with n + 1 faces. By our inductive hypothesis, you can color this map (with the one face removed) with at most six colors. Color it. Now you need to decide on how to color the removed face. This is easy! Notice that there are at most five neighbors to this face and they have colors red, blue, green, yellow, orange. Here is a representative picture.

You have one more color to play with. Use it to color the removed country. You are done! **QED. **

So far we have shown that 6 colors suffice for standard maps (every vertex meets exactly three edges. The jump from standard maps to all maps is pretty easy to do.

**Proof of Theorem A:** For each vertex that meets more than three edges, draw a small circle around that vertex and erase the portions of the edges that lie in the circle. Here is a representative example.

Note that this map is now a standard map (each vertex meets exactly three edges). Theorem B says we can color it with at most 6 colors. Color it. Now remove the disks, extend the edges to their original meeting place, and extend the colors to the affected regions. This will be an allowed 6 coloring. **QED.**

Final note: If one is willing to extend this proof and work through a few more technical details, one can prove the 5 color theorem. We refer the ambitious student to Conway’s book Mathematical Connections – where I got the above proof of the 6 color theorem.