March 1, 2013 | 7
The 4-color theorem is fairly famous in mathematics for a couple of reasons. First, it is easy to understand: any reasonable map on a plane or a sphere (in other words, any map of our world) can be colored in with four distinct colors, so that no two neighboring countries share a color.
Second, computers were instrumental in the proof of the four-color theorem. The theorem had been suggested in 1852 as a conjecture, but people were unable to prove it until 1976, when Kenneth Appel and Wolfgang Haken reduced the problem to a number (1936, to be precise) of specific cases and wrote a computer program to check each case. It was the first major theorem to be proved using a computer, and for some people, it raised questions about what it means to prove a theorem. Did this computer proof “count?” Were mathematicians going to be obsolete soon? People are still debating the role of computers in mathematical proof and the future of mathematics as a human endeavor.
But that’s not what I’m here to talk about. Instead, I want to have fun coloring maps. A few weeks ago, I was visiting a friend who is a math instructor at a community college. She was getting ready for an outreach event for middle-schoolers, and one of the topics she was going to talk about was the 4-color theorem.
Neither of us was all that familiar with the 4-color theorem, so the first thing we did was try to figure out exactly what the rules for the theorem should be. It seems pretty obvious that if one is sufficiently mischievous, one can draw bizarre maps that don’t satisfy the theorem. After doodling a bit, we figured out that disconnected regions are a no-no. If a country comes in two pieces (like the US, which has Alaska and the lower 48 as two separate regions), you can’t guarantee that both regions can be colored the same color and still get a 4-colorable map. It was a little harder to figure out that a country shouldn’t have a hole in it, or completely surround another country or countries.** Africa is 4-colorable, but technically South Africa, which completely surrounds Lesotho, doesn’t fit the hypotheses of the theorem. Also, regions that touch only at a corner, like Utah and New Mexico, are allowed to be the same color. Without that rule, we could create a pizza-shaped country with as many slice-shaped states as we wanted, and each state would require its own color.
The next obvious question to ask is whether any maps actually require four colors. After all, before there was a 4-color theorem, there was a 5-color theorem. Should we really have a 3-color theorem? No. There are maps that require four colors. A real-world example is Austria. It is surrounded by a ring of seven* countries, and as you can see in the picture below, this poses a problem.
After we figured out the rules for the 4-color theorem, we wanted to see whether it was easy or hard to come up with a 4-coloring of a map. My friend printed out a map of continental Europe minus most of Scandinavia (just to make it big enough for satisfying coloring. We have nothing against Scandinavia. Mmm, salty licorice!), and then we started coloring. It was actually quite soothing. The first map I made, I tried for a nice balance of colors. I started at Austria because I knew it was a problem country (not in real life! Mmm, schnitzel!), and there was one moment around Lithuania when I almost messed up and created the need for a fifth color, but I managed to avoid it. My resulting map is at the top of this post.
For my second map, I was aiming for a “least” 4-coloring, meaning how much could I get done with the first two or three colors? I started at the west and tried to use just orange and blue for as many countries as possible. Then I used purple as much as possible before resorting to green. I only ended up with four green countries, although I did use it for Ukraine, which is large.
My “greedy” coloring might not be the optimal one. I just made it up as I went along, moving from left to right, and there might be better ways to do it that minimize either the number of countries that are colored purple and green or the total area of the map that is colored purple and green. I can already see that just by switching Poland and Ukraine, I could have used less green without messing anything else up. That got me wondering how one might develop an algorithm for minimizing the number of countries or area that uses the fourth color, and whether you might sometimes minimize the area at the expense of adding another country in the fourth country.
I didn’t learn anything profound while I was coloring maps, but if I were in the business of proving theorems about maps, this might have been a good way to develop my intuition. My “greedy” coloring helped me formulate a couple of questions about map coloring, and in mathematics, asking good questions is almost as important as being able to answer them. If you’d like to develop your four-coloring skills, there’s a colorable map of Europe here.
*Austria is actually surrounded by eight countries, but Liechtenstein’s border with Austria is entirely surrounded by Switzerland’s border with Austria, so it doesn’t change the number of colors required. In other words, if Switzerland annexed Liechtenstein, we would still need four colors to color the region of the map around Austria. But if it annexed Germany instead, we would only need three colors. This is actually an even-odd issue. On a map of the US, you can compare the region around Nevada to the region around Utah to study this phenomenon for yourself.
**Update March 5, 2013: This sentence is incorrect, as is the next one. I wrote a follow-up post describing why regions with holes in them don’t interfere with 4-colorability.