Caleb Stanford Blog

3 facts about the 4-color theorem


Here are some facts about the four color theorem.

1. There is always a way to color the outer region as well.

Take a look at this 4-coloring of the US map, from the Wikipedia page:

4-colored US map

It’s technically suboptimal because white is a color, too, and they used white for the outside! For some reason, this bothers me. It’s in fact always possible to color the entire map, including the outer region, with 4 colors. Here, I did it in Pinta image editor to show you:

4-colored US map including outer region

(Note that Utah / New Mexico and Arizona / Colorado must be considered non-adjacent for the 4-color theorem to apply.)

2. The regions can have holes!

The 4-color theorem is valid even if not all of the regions are topologically disks; they can have holes. In fact, point #1 was already an example of this, since the outer region has one big hole. But it’s true more generally. However, the regions certainly can’t be “adjacent” to themselves, and also, they must be contiguous regions. Which brings us to:

3. The theorem doesn’t technically apply to real maps, including the US map.

Why not? Because real maps have countries and states that are split into multiple non-contiguous parts. In the US, that’s just the state of Michigan, but there are probably much worse examples world-wide. This blog post discusses it in detail and concludes that, as of July 2016, the globe still happens to be 4-colorable. (I guess that means 5-colorable if you include the color of oceans / water.)

Anyway I would def buy a globe that was 5-colored where blue is reserved for all bodies of water and countries which have multiple pieces are colored the same. That would be a cool thing to have.

Edited on .