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

### Why Not Five Colors, All Touching?

```Date: 04/30/2003 at 03:58:01
From: Joanna
Subject: Five colors, all touching?

My 4th-grade class was instructed to use 5 colors for the problem I'm
about to describe. With 5 colors we were supposed to create a
situation in which all colors were touching each other color
simultaneously. When two of the colors were touching at points or
corners, that didn't count as "touching."  For example, you could not
evenly slice up a pentagon - assign each 'piece' a color, and
therefore say you've solved the problem.

So when I say that each color has to touch all the other colors: -
Blue, Green, Yellow, Orange, Red - B has to touch G,Y,O,R, and G must
be touching B,Y,O,R, etc. It must be 5 "blobs" or whatever shape you
need to achieve this. It can't be more than 5, though.

I am able to create a situation in which 4 of the colors are touching
the other colors. It comes down to one final color being isolated, or
surrounded, by the other colors and therefore not allowing one final
color to touch it to complete the promblem.

The work is totally visual. I have gone through several sheets of
paper sketching out different scenarios and I can't conjure up the
solution. One color always remains cut off.
```

```
Date: 04/30/2003 at 20:29:18
From: Doctor Ian
Subject: Re: Five colors, all touching?

Hi Joanna,

This is easier to think about if we use graphs, rather than shapes.
Suppose we make a shape like

+---+---+
| a | b |
+-------+
|   c   |
+-------+

We can represent each region as a node in a graph.  An arc between two
regions means that there is a border between the regions:

a-------b
\     /
\   /
\ /
c

Now, suppose we add a fourth region, which touches all the others.  It
might look like this,

+--------+
|      d |
+---+---+  |
| a | b |  |
+-------+  |
|   c   |--+
+-------+

or it might look like something else, but on our graph, we really have
only two choices for where to put d, so that it can connect to all the
other regions.  It can go inside,

a-----------------b
\ .           . /
\   .     .   /
\     d     /
\    .    /
\       /
\  .  /
\   /
\ /
c

or it can go outside,

. . . . . . d
.         . .
.        .  .
a-------b   .
\     /   .
\   /   .
\ /   .
c . .

And in fact, these are really the same case: one in the middle,
connected to the other three. (Just switch the labels 'b' and 'd',
and one graph turns into the other.)

Now, when we try to add a fifth region, what will happen in our graph?
If it goes outside the triangle,

a-----------------b
\ .           . /
\   .     .   /
\     d     /
\    .    /
\       /        e
\  .  /
\   /
\ /
c

then we can't get to the region that's surrounded without crossing an
existing border (i.e., breaking up one of our regions).  But if we go
inside the triangle,

a-----------------b
\ .    e      . /
\   .     .   /
\     d     /
\    .    /
\       /
\  .  /
\   /
\ /
c

then we've surrounded the new region with three regions, and cut off
the fourth. What you're always going to find is that the fourth region
you add cuts off one of the others.

So it's not surprising that you haven't been able to find the
arrangement you're looking for. What would be surprising is if you
_did_ find it!

See the Dr. Math archives (and you can find more examples using the
Dr. Math searcher at
http://mathforum.org/library/drmath/mathgrepform.html
to look for the keywords  four color theorem  ):

Four-Color Theorem
http://mathforum.org/library/drmath/view/57256.html

The Four Color Map problem
http://mathforum.org/library/drmath/view/52466.html

Four Color Map Problem
http://mathforum.org/library/drmath/view/57231.html

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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