How many colors does it take to be able to color any map,
so that no two adjacent countries have the same color?
The famous **Four-Color Map Theorem**
answers this question for maps on a plane,
or on the surface of a sphere.
But on a torus, the number isn't four -- it's seven.
(A **torus** is a shape like the surface of a donut.)

This gives us a little puzzle: Find a map on the torus that requires seven colors. This page gives two general hints on how you might go about doing this; the next page shows some pictures of a solution, including a couple basic Quicktime animations.

**Hint One:**
Note that
the shape of the countries doesn't matter;
what matters is which ones touch each other.
Instead of drawing the borders, we can just
draw a point somewhere in the middle of each country
to represent that country,
and for each two countries that touch,
draw a line from the one point to the other.
This graph is called the
the **dual** of the map.
It tells us everything
we need to know about the map, and it's easier
to deal with.
As long as the lines don't cross, every graph
can be turned back into a map.
(To do this, just take the graph's dual! The dual of the dual
of a map is the same map -- or at least, a topologically
equivalent one.)

**Hint Two:**
It's easier if you first unwrap the torus into a rectangle.
(Drawing on a donut with a pen is just a big mess;
even a bagel isn't much help.)
Imagine cutting through one side of the torus,
and then straightening it out to make a long tube.
Then slit the tube along its length.
You are left with a rectangle.
It can be rolled back up into the torus by
zipping together the top and bottom (making the cylinder again),
then zipping together the left and right sides.

You can draw on the rectangle, as a way of representing
drawing on the torus. Just remember that the points along
the top edge are really the same points as the points along
the bottom edge (A=A, C=C), and similarly for the left and right edges (B=B).
So when you cross over the top edge (1),
you come back on the bottom (2);
similarly, if you go off the right edge (2),
you come back on the left (3).
(Those who have played video games like
*Asteroids*
are quite familiar with this topology.)

(Here is an equivalent, though perhaps more mind-bending,
viewpoint. Consider
tiling
the plane with infinitely many copies of the rectangle.
If you draw on one rectangle, you draw on them all;
if you go off the right edge of a rectangle,
you come back on the left edge of another copy of it.
Nina Amenta's program
Kali
lets you draw this way; it was used to draw the picture at left.
Hints on using Kali:
Select symmetry "0". Double-click to raise the pen up.)

Click here when you're ready to see a solution to the puzzle.