ADVERTISEMENT
  About the SA Blog Network













Roots of Unity

Roots of Unity


Mathematics: learning it, doing it, celebrating it.
Roots of Unity Home

Wrong in Public: the 4-Color Theorem Edition

The views expressed are those of the author and are not necessarily those of Scientific American.


Email   PrintPrint



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.

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.

 

A hypothetical region that violates 4-colorability with a hole-y country.

“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.”

The large, no-longer-hole-y country still touches all the bordering countries.

“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!

Evelyn Lamb About the Author: Evelyn Lamb is a postdoc at the University of Utah. She writes about mathematics and other cool stuff. Follow on Twitter @evelynjlamb.

The views expressed are those of the author and are not necessarily those of Scientific American.



Previous: Having Fun with the 4-Color Theorem More
Roots of Unity
Next: Time in 298 Words




Rights & Permissions

Comments 6 Comments

Add Comment
  1. 1. DrMathochist 10:09 am 03/5/2013

    This ties back into what I consider the first “proof” I ever constructed wholly on my own. In 5th grade math class, we were presented with the 4CT via a not-uncommon story: a farmer dies and wills his land to his five sons, to be divided in such a way that [description of a non-4-colorable map]. We were set to finding a way to do this, only to be gathered back together later and told that it’s actually impossible; that’s the 4CT.

    But I wasn’t satisfied, and for much the same reason you raised about the ocean. “If only,” I thought, “the outer part could reach around and touch the inside somewhere.”

    The next Monday I showed up with a styrofoam torus, purchased at a local hobby store, painted with seven regions, all touching each other (which turns out to be the maximum on a torus). The assumption that the graph is planar — or, equivalently, that it can be drawn without crossing arcs on the surface of a sphere — is essential to the 4CT. My reasoning: the problem NEVER EXPLICITLY STATED that the farmer’s land was not, in fact, on the surface of an asteroid with a hole in it.

    Link to this
  2. 2. Autaut 12:20 pm 03/5/2013

    I really like your story, DrMathochist!
    Hope your teacher appreciated your investigation :)

    Link to this
  3. 3. JoeMerchant 1:10 pm 03/5/2013

    111111
    155551
    222351
    233351
    244451
    145551
    111111

    1 borders 2, 3, 4 and 5
    2 borders 1, 3, 4 and 5
    3 borders 2, 4 and 5
    4 borders 1, 2, 3, and 5
    5 borders 1, 2, 3, and 4
    If:
    1 is blue
    2 is red
    3 is green
    4 is yellow
    which of those four colors can 5 be?

    Link to this
  4. 4. Evelyn Lamb in reply to Evelyn Lamb 2:03 pm 03/5/2013

    1 doesn’t border 3, so they can be the same color.

    Link to this
  5. 5. Autaut 2:08 pm 03/5/2013

    3 can be 1, so 5 is actually the 4th color.

    Link to this
  6. 6. Cahit 7:42 am 03/11/2013

    The proof of the four color theorem is to show that all maximal planar graphs can be colored at most four colors where the faces (including the outer-face) of the maximal planar graph are triangles. Let us consider a maximal planar graph in which, except the outer-cycle all faces are triangles. Then we have to show that for all such maximal planar graphs there exists four coloring such that outer-cycle colored with only three colors. Hence from here we say that all maximal planar graphs are four colorable. I have given short algorithmic proof of the four color theorem based on spiral chain coloring algorithm. Critical point in my proof is the maintaining three colorability of the outer spiral segment. Details along the other proofs can be found in my paper:

    http://www.academia.edu/541633/On_the_Algorithmic_Proofs_of_the_Four_Color_Theorem

    Link to this

Add a Comment
You must sign in or register as a ScientificAmerican.com member to submit a comment.

More from Scientific American

Scientific American Dinosaurs

Get Total Access to our Digital Anthology

1,200 Articles

Order Now - Just $39! >

X

Email this Article

X