Associated Topics || Dr. Math Home || Search Dr. Math

### The N-Color Theorem?

```Date: 07/27/2002 at 07:50:56
From: John Choi
Subject: Eight Color Map Problem???

While thinking about the Four Color Map Problem, I came up with an
idea: If a polysected plane really does only need four colors to color
it in with no same color touching, then it could be a pattern with 1-D
maps and even 0-D maps!

So I thought briefly about a 1-D map(obviously a line segment), and
came up with 2 colors for the required number of colors. And when I
looked up 0-D (I guessed a point would be 0-D), I came up with 1
(obviously).

Ah-ha! I saw a pattern! Maybe the maximum number of colors
required to fill a polysected n-D space would require 2^n colors?

So that would mean 8 colors maximum would be needed to completely
fill a multi-divided space with no adjacent sections the same color?
might have just discovered (well, at least hypothesized) a new and
important rule.

Could you please tell me what you think about it? And if you think
it's wrong, why you think so? Or if anyone else has ever thought this
before? Or if I'm the first in the world, and it COULD be true, then
where I should report my amazing discovery? Thanks!

Sincerely and excitedly,

John Choi
Currently Residing in South Korea
```

```
Date: 07/30/2002 at 21:02:59
From: Doctor Peterson
Subject: Re: Eight Color Map Problem???

Hi, John.

This is an interesting conjecture, but of course until you have some
evidence, it's not worth much. And as much fun as it can be to make
conjectures, it's a lot more fun to find a proof - even if it's a
proof that your conjecture is wrong.

My first impression when I saw your question was that probably the
three-dimensional case is not nearly as interesting as you would
think. Why? First, because if it were interesting I would have heard
of it; second, because my experience with 2- and 3-dimensional
problems tells me that when you move up to three dimensions there is
so much more flexibility that problems like this tend to become
either impossible or trivial. Notice that in 0 and 1 dimension your
problem was trivial, but in 2 dimensions it was an extremely hard
problem. We can expect it to be different again in 3.

So let's try making a dissection of space that requires lots of
colors, in order to attempt a disproof, or at least learn how
coloring works in space. A trick I like to use in solving problems is
to work backward: rather than trying to cut up space, which can be
hard to visualize, I'd like to build up space out of different-
colored pieces so that each touches all the others and each has to be
a different color.

I struggled a bit trying to find a good way to make my intuition
concrete, then realized I should take myself literally and use
something "flexible": a rope! Suppose I have eight ropes of different
colors, and just drop them in a tangle on the floor. There's a good
chance that they will all touch one another, isn't there? Can we
prove that this is possible? My first thought was to use a
complicated braid; but then I saw that I can use just the most basic
idea behind a braid, a crossover. So lay your eight ropes out
parallel, and then just flip the whole row over itself:

+   +   +   +   +   +   +   +
/ \ / \ / \ / \ / \ / \ / \ / \
/   \   \   \   \   \   \   \   \
/   / \ / \ / \ / \ / \ / \ / \   \
/   /   \   \   \   \   \   \   \   \
/   /   / \ / \ / \ / \ / \ / \   \   \
/   /   /   \   \   \   \   \   \   \   \
/   /   /   / \ / \ / \ / \ / \   \   \   \
/   /   /   /   \   \   \   \   \   \   \   \
/   /   /   /   / \ / \ / \ / \   \   \   \   \
/   /   /   /   /   \   \   \   \   \   \   \   \
/   /   /   /   /   / \ / \ / \   \   \   \   \   \
/   /   /   /   /   /   \   \   \   \   \   \   \   \
/   /   /   /   /   /   / \ / \   \   \   \   \   \   \
/   /   /   /   /   /   /   \   \   \   \   \   \   \   \
/   /   /   /   /   /   /   / \   \   \   \   \   \   \   \

Each rope now touches each of the others, so we can't use fewer than
eight colors.

If you don't think this looks enough like a dissection of space, just
glue the ropes together where they meet to make sure they stay in
contact, and let each one puff up to fill as much of space as it can.
Or, spray foam over the whole thing, making a ninth region that fills
the rest of space. Now you need nine colors.

And, of course, there was nothing special about the choice of eight
ropes. We could have used any number; so there is no limit to the
number of colors you might need.

This is a nice example of the kind of thinking mathematicians do. We
can visualize an idea in various ways, trying to make our general
sense of what is happening specific enough that it can be turned into
a formal proof. I haven't done that last step here, but it's clear it
can be done.

So your conjecture turns out to be false; but it led to some
interesting ideas on the way to its disproof, didn't it? Now we know
why I never heard of anyone writing a thesis on this subject!

If you have any further questions, feel free to write back.

- Doctor Peterson, 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search