Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Mobius Strips and the Six-Color Map Theorem


Date: 12/16/98 at 07:36:16
From: Jason Boomer
Subject: Moebius strips

In the four-color map theorem, any flat map divided into "countries" 
can be colored with four distinct colors, so that no country touches 
another of the same color. The book _Mathematics_ from the Life Science 
Library says about the six-color map theorem, 

   "On a mobius strip, six colors are needed to ensure that no 
    bordering areas on any map will be colored the same. Although a 
    flat map can be drawn on an ordinary paper band using only four 
    colors, if the band is twisted into a mobius strip the same map may 
    require six colors."

Our question is, isn't it simple to make a map that doesn't fit that 
rule?  If it has the same color on opposing corners, won't two of the 
same color touch?   

Here is a slightly different question. Not only did we come up with a 
mobius strip with six colors that doesn't work, simply by putting the 
same color in opposing corners and opposing ends (the mobius strip 
should be colored the same on both sides, by the way), but we have also 
come up with one that requires fewer than six colors that does work.  
You can do it with just two colors if you simply divide the band in 
half, coloring one half one color and the other another, or make it a 
checkerboard pattern, and it will still work. So can you tell us: if 
the book says it takes six colors, why you can make one with six that 
doesn't work, and one with two that does?


Date: 12/16/98 at 13:37:00
From: Doctor Schwa
Subject: Re: Mobius strips

Both of these questions have the same answer. The coloring theorem only 
says that if you draw any map on a mobius strip then it is POSSIBLE to 
color it with AT MOST 6 different colors so that no two adjacent 
regions have the same color.

If you find that two adjacent regions have the same color so that it 
looks as if you need more than six, just start over coloring it in a 
different way and you'll find it's always possible to find SOME way of 
coloring that works using at most six colors.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/   


Date: 12/16/98 at 13:45:01
From: Doctor Rob
Subject: Re: Mobius strips

If you color both sides of a flat strip of paper, using four colors, 
and then twist it into a Moebius strip, there may well be one or more 
pairs of touching countries of the same color. That means you will have 
to change the color of one of each such pair. This in turn may force 
changes to countries touching that one, and so on. It is difficult to 
predict the cascade of changes that might be necessary. 

That is why it is not obvious that six colors would suffice for any 
map, and that there is at least one map where six colors are required. 
It is clear that eight would be enough, by just using four colors on 
one side and four different colors on the other side of the piece of 
paper.  It is also clear that there are maps requiring four colors, 
since that is true on both sides of the flat piece.

Remember, you only need one example of a map requiring six colors! It 
is not necessary for every map to require six colors. The standard 
example for a Moebius strip is to divide its surface into thirds 
lengthwise with two lines. Then cut the part adjacent to the edge into 
sections, each roughly rectangular, and do the same with the center 
part. When cut apart and flattened, the resulting map looks like this:

First side:

    o---------------------------------------o-------------------o
   C|                   1                   |         2         |A
    o---------o---------o---------o---------o---------o---------o
   B|    4    |         5         |         6         |    10   |B
    o---------o---------o---------o---------o---------o---------o
   A|         8         |                   9                   |C
    o-------------------o---------------------------------------o
        
Flip over top-to-bottom to see the second side:

    o-------------------o---------------------------------------o
   A|         2         |                   3                   |C
    o---------o---------o---------o---------o---------o---------o
   B|    10   |        11         |        12         |    4    |B
    o---------o---------o---------o---------o---------o---------o
   C|                   7                   |         8         |A
    o---------------------------------------o-------------------o

Here A and B are cuts through the middle of regions numbered 2, 4, 8, 
and 10, and C is a border between regions numbered 1 and 3 and between 
7 and 9. There are 12 regions all together.

If you inspect this carefully, you will see that each region borders on 
five others, so must have a color different from all of theirs. If you 
try to color this, you will soon find that six colors are required.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   


Date: 04/24/2000 at 08:35:13
From: Bob Sundling
Subject: Error in "Mobius Strips and the Six-Color Map Theorem"

In Dr. Rob's answer to "Mobius Strips and the Six-Color Map Theorem" it 
is stated that one needs six colors to color a map on a Mobius strip, 
and he gives an example.

Both the statement and Dr. Rob's example are incorrect.

He forgets that a Mobius strip is isomorphic to the area bounded by two 
concentric circles on a plane (loosely, a "ring"). The Four-Color Map 
Theorem therefore DOES apply to maps drawn on Mobius strips, unless one 
inadvisably considers two areas to be neighbors when they touch 
"through" the paper, i.e. are in the same place on opposite sides of 
the paper of the strip. However, in Dr. Rob's example map, he says each 
region has exactly five neighbors, so this is NOT the case here.

Here is the map from the original problem, with the original region 
numbers, this time drawn as a "ring" on a plane:

     o--------------------------o----------------o
     |                1         |                |
     |   o-------o---------o----o----o-------o   |
     |   |       |    5    |    6    |       |   |
     |   |   o---o----o----o---------o---o   |   |
     |   |   |        |         9        |   |   |
     |   |   |   o----o--------------o   |   |   |
     |---| 4 | 8 |                   |---|10 | 2 |
     |   |   |   o----o--------------o   |   |   |
     |   |   |        |        7         |   |   |
     |   |   o---o----o----o---------o---o   |   |
     |   |       |   12    |   11    |       |   |
     |   o-------o---------o----o----o-------o   |
     |                3         |                |
     o--------------------------o----------------o

That his map, or any map on a Mobius strip, therefore obeys the Four-
Color Map Theorem is obvious since they can be drawn on a plane. But to 
illustrate, you can color the regions in his map as follows:

      1 - Blue
      2 - Red
      3 - Green
      4 - Red
      5 - Green
      6 - Orange
      7 - Green
      8 - Orange
      9 - Red
     10 - Blue
     11 - Orange
     12 - Blue

To check that this works, we can check the neighbors:

      1 borders 2, 3, 4, 5 and 6. None are blue.
      2 borders 1, 3, 6, 10, and 11. None are red.
      3 borders 1, 2, 4, 11, and 12. None are green.
      4 borders 1, 3, 5, 8, and 12. None are red.
      5 borders 1, 4, 6, 8, and 9. None are green.
      6 borders 1, 2, 5, 9, and 10. None are orange.
      7 borders 8, 9, 10, 11, and 12. None are green.
      8 borders 4, 5, 7, 9 and 12. None are orange.
      9 borders 5, 6, 7, 8, and 10. None are red.
     10 borders 2, 6, 7, 9, and 11. None are blue.
     11 borders 2, 3, 7, 10, and 12. None are orange.
     12 borders 3, 4, 7, 8, and 11. None are blue.

This also helps to illustrate that there is a BIG difference between 
the two statements "each region borders on five others" and "six colors 
are required."

Bob Sundling (BS Mathematics, UW-Madison)


Date: 04/25/2000 at 10:47:25
From: Doctor Rob
Subject: Re: Error in "Mobius Strips and the Six-Color Map Theorem"

Bob,

On further reflection and consultation of sources, I believe you are 
laboring under a misconception.  The annulus that you say is isomorphic 
to the Moebius strip is orientable. The Moebius strip is not. Thus they 
cannot be isomorphic. I believe your disagreement with my statements is 
rooted in the definition of the idea of coloring a surface. You seem to 
want to paint each "side" of the surface. This is not the usual 
definition, which involves a region of the surface, bounded by a simple 
closed curve, for which a uniform color is assigned to all its points, 
and therefore to the region. That means that "both sides" of each 
region have the same color. Clearly for an orientable surface, which 
viewpoint you take is immaterial, but for nonorientable ones, it makes 
a big difference!

This is in agreement with the following reference:

     Tietze, Heinrich, _Famous Problems of Mathematics_ (New York: 
     Graylock Press, 1965), especially Chapter IV, "On Neighboring 
     Domains," and Chapter XI, "The Four Color Problem."

There, on p. 233, Tietze says, "Ironically enough, the coloring problem 
has not been solved for many of the orientable surfaces, whereas it has 
been completely solved for the nonorientable ones [8]; for example, 
chi = nu = 6 for the Moebius band (see Figs. 40, 41 and Plate VI)." 
Here chi is the chromatic number, which is the minimum number of colors 
necessary to color any map, and nu is the maximum number of mutually 
neighboring domains. The reference [8] is:

     Heawood, P. J., _Quarterly Journal of Mathematics, vol. 24 (1890), 
     and vol. 29 (1898).

Figures 40 and 41 show the Moebius band. Plate VI shows an example 
which allegedly requires six colors, and which is equivalent to this 
layout:

    o-------------------------------o-------------------------------o
   C|               1               |               2               |A
    o-------o-------o-------o-------o-------o---------------o-------o
           B|       5       |       6       |       4       |B
            o-------o-------o-------o-------o-------o-------o
                   A|               3               |C
                    o-------------------------------o

The edges labeled A, those labeled B, and those labeled C are to be 
joined in pairs, after the traditional half-twist. Remembering that the 
colors are the same on both "sides" of each region, you can see that 
each region shares a border with all of the other five regions, and so 
six colors are required.  Thus the statement that six colors are 
required for a Moebius strip is correct.

Another way to look at this is in terms of the graph that is the dual 
of the map. Pick a point in each region. If two regions share a border, 
connect them with an edge. This gives you an undirected graph. Color 
the vertices so that no edge has the same color at both ends. This is 
equivalent to coloring the regions. The graph of the above example is a 
complete graph on six vertices, that is, each vertex is connected to 
all five of the others. That implies that six colors are necessary.

I see that the example I gave on the web page in the archives falls 
into the same trap that I described above, about painting the different 
"sides" of a region different colors. I will change that part of our 
archived answer, together with including a discussion of coloring of 
regions versus coloring of "sides" of regions.

Thank you for making me examine this situation in great detail. It has 
improved my understanding of the problem.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
College Discrete Math
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/