See Inside

Oddball maps can require more than four colors

Science operates according to a law of conservation of difficulty. The simplest questions have the hardest answers; to get an easier answer, you need to ask a more complicated question. The four-color theorem in math is a particularly egregious case. Are four colors enough to identify the countries on a planar map, so that two bordering countries (not counting those that meet at a point) never have the same color? The answer is yes, but the proof took a century to develop and filled a 50-page article plus hundreds of pages of supplementary material.

More complicated versions of the theorem are easier to prove. For instance, it takes a single page to show that a map on a torus requires at most seven colors. The latest example of unconventional cartography comes from philosopher Hud Hudson of Western Washington University in a forthcoming American Mathematical Monthly paper. He presents a hypothetical rectangular island with six countries. Four occupy the corners, and two are buffer states that zigzag across the island. The twist is that the zigs and zags change in size and spacing as they go from the outskirts toward the middle of the island: each zigzag is half the width of the previous one. As the zigzags narrow to nothingness, an infinite number of them get squeezed in.

Already a Digital subscriber? Sign-in Now
Rights & Permissions

View
1. 1. andrewxc 07:37 AM 10/30/09

In a Combinatorics class that I took recently, our professor handed this out. I was able to show that it does not, in fact, require six colors.

Label the regions 1-6 in the graphic: 1) Top-left, dark blue; 2) Bottom-left, blue; 3) Snaking-left, light blue; 4) Top-right, dark green; 5) Bottom-right, light green; 6) Snaking right, yellow.

1, 2, and 3 all touch and must be different colors. 1 & 4 touch and must be different colors, as well, but 4 does not touch 2 OR 3, since the boundary pattern continues indefinitely, so 4 is either color 2 or 3 (your choice). Similarly for 5 and even 6 (3 & 6 never cross the center boundary and so never touch the outer 1, 2, 4, or 5 opposite them). So we only require 3 colors for this graph.

If we assume that any of these regions DO touch ("at infinity"), we may prove (by the Four-Color approach) that all of the others cannot and must be the same color.

If you insist that the Quantum Mechanical view is appropriate, that it is impossible to determine which regions are touching "at infinity" and therefore all of the cases must simultaneously be true, then a) the hallway is not infinite and b) I will refer you to the "hallway analogy" that I constructed:
Assume that you start painting this pattern on a wall, and that the infinitely decreasing snaking regions start moving down a hallway of infinite length. Regions 1 & 4 touch at the ceiling, 2 & 5 on the floor. 3 & 6 may be of any size, but may not themselves touch on the ceiling or floor. Continue down the hallway forever. Regions 3 & 6 will never touch each other because they are on opposite walls, 2 & 4 will not touch each other because they are directly opposite each other (left-floor and right-ceiling), separated by regions 2, 3, 5, and 6.

I don't doubt that this was disproved back in 2003, but our professor never showed us that letter.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Scientific American Magazine | 1 hour ago

### Orphaned Chimpanzees Play Rougher Than Their Mother-Reared Counterparts

• Scientific American Magazine | Dec 7, 2013

### Teenage Flu Scientist Shares His Recipe for Prizewinning Research

• Scientific American Magazine | Dec 7, 2013

• Cocktail Party Physics | Dec 7, 2013

### Physics Week in Review: December 7, 2013

• @ScientificAmerican | Dec 6, 2013

More »

## Latest from SA Blog Network

• ### Stream of Thought Description of Teaching James's "Stream of Thought": A Work of Faction

Cross-Check | 21 hours ago
• ### Physics Week in Review: December 7, 2013

Cocktail Party Physics | Dec 7, 2013
• ### Wonderful Things: The Pugnacious, Alien-esque Skeleton Shrimp

The Artful Amoeba | Dec 6, 2013
• ### Can We Harness Disruption to Improve Our World's Future?

STAFF
@ScientificAmerican | Dec 6, 2013
• ### British Storm Brings Up History's First Work of Social Media

Plugged In | Dec 6, 2013

## Science Jobs of the Week

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X