This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
Wrong in Public is a new, hopefully very occasional, series on Roots of Unity. I don't like being wrong in public, but sometimes I make a mistake in a post, and sometimes mistakes are interesting.
In last Friday's post on the 4-color theorem, I talked about some of the hypotheses of the theorem, including the fact that countries or states need to be connected in order for the theorem to apply. In other words, we aren't guaranteed to be able to color a map with only four colors if I demand that both the Upper Peninsula and "mitten" of Michigan be colored green. I also said, "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." This is not true. One of my readers kindly pointed out my error by email and included some detailed explanations of how to see that countries with holes don't jeopardize 4-colorability.
It is clear that one country sitting inside another country—Lesotho in South Africa, for example—does not pose an obstacle to 4-coloring. Lesotho can be colored with any color other than the one used for South Africa, and the color used for Lesotho doesn't affect the color that can be used for Namibia or Botswana.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
I wasn't thinking of a simple situation like South Africa/Lesotho when I said that a country shouldn't have a hole in it. I was thinking of a more complicated situation involving a hole-y country. My reasoning was that we could take a region of a map that required four colors and then surround it by a country that touches all the countries of the region. The surrounding country couldn't be colored with any of the four colors we had already used, so we'd have to add an extra color. Logical enough, no? The only problem is that it's wrong. (I'd like to add that I did try to "experimentally verify" this situation with a little drawing, and I thought I had succeeded. I don't have the drawing anymore, but there was something wrong with it. In my defense, I was coloring with a friend, not writing a math paper.)
The 4-color theorem isn't exactly a theorem about maps and globes as we usually think of them. We can strip away some details—the sizes and shapes of countries, the locations of rivers and mountain ranges, and so on—as long as we keep all the information about which countries border each other.
This figure shows how a graph can be extracted from a map. The black dots, or vertices, represent countries, and the lines between them show how the countries are connected. Image: Ingrid Daubechies, Shannon M. Hughes, and Dan Katz.
By using graphs, we can reduce a complicated map, which contains a lot of unnecessary information, to something easier to understand and deal with. The vertices of the graph are the countries, and edges represent borders between countries.
A graph representing a portion of a map of Europe. Without the details of sizes and shapes of countries, the connections between countries are clearer. Image: Ingrid Daubechies, Shannon M. Hughes, and Dan Katz.
A graph that comes from a map will always have a special property: it can be drawn so that none of its edges intersect. Graphs with this property are called planar. We can now state the 4-color theorem in the language of graph theory. Every planar graph can have its vertices colored with four colors in such a way that no edge connects two vertices of the same color.
Kai Frederking, the reader who pointed out my mistake, told me about a fact from graph theory that I didn't know. It's about the vertices that make up the "outside" of the graph, in other words, the vertices that are not completely surrounded by edges. In the case of the Earth, the outer vertices are the countries that touch the ocean. As the name indicates, an outerplanar graph is a planar graph in which all vertices are outer vertices. The fact I didn't know is that outerplanar graphs are 3-colorable.
This fact fixes everything! If we have a country that has a hole in it, we only need to worry about the portion of map contained inside that country. The inner countries that border the surrounding country only require 3 colors because they form an outerplanar graph, so we have a fourth color available to color the surrounding country. We still have to worry a little about the rest of the countries inside the surrounding country, and the full argument is out of the scope of this blog post, but the 3-colorability of the countries just inside the surrounding country is the crux of the argument.
Mr. Frederking also shared a more intuitive explanation for why a hole-y country is allowed. He said it very well, so I'll just use his words. "The intuitive approach is to assume a map with an area enclosing a set of countries, say an ocean, that violates 4-colorability," he wrote.
"Now imagine cutting a corridor through the enclosing country in such a way that it no longer surrounds those in the middle, but still touches all of them."
"If 4-colorability was violated before, it still will be violated, since no touching borders have been removed (we just cut a circle in one place). So we would be able to construct a non-4-colorable map without enclosed areas, in contradiction to the 4-color theorem." In other words, we can make it so that the large, surrounding country doesn't have a hole without changing the graph that represents the region.
This is actually really cool. It means the ocean can participate in a 4-coloring of a map. We can color the ocean with one color (might I suggest blue?), and the rest of the map can still be 4-colored around it. The one drawback is that we can't specify that blue means water. There will be some landlocked countries colored in blue, maybe Paraguay or Mongolia, but that's the price we pay for maximally efficient cartography.
As a bonus, we've also learned that the coastal countries form a 3-colorable sub-map of the Earth. We know that the map as a whole, including the ocean, is 4-colorable, so we also know that we can color everything that touches the ocean with the remaining 3 colors. Of the 169 Sporcle-recognized countries, only 45 are landlocked, and Wikipedia, although it has a slightly different definition of "country" than Sporcle due to its inclusion of some disputed regions, says landlocked countries only cover 11.4% of the land area of the Earth. So most of the Earth can be represented by a 3-colorable map. I think that's pretty cool.
The source of the map-to-graph illustrations I used in this post is this pdf. If you're interested in exploring some of the ideas of graph theory as it relates to colorability of maps, I think it's a nice introduction that doesn't require much prior mathematical knowledge. By the end of the notes, you get to prove the 6-color theorem, which is weaker than the 4-color theorem but a lot more digestible.
That concludes today's edition of Wrong in Public. I hope it's a long time before the next one!