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

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

• News | 4 hours ago | 3

### Will Great Wines Prove a Moveable Feast under Global Warming?

• The Thoughtful Animal | 5 hours ago

### Once Upon A Time, The Catholic Church Decided That Beavers Were Fish

• Guest Blog | 6 hours ago

### The Art and Science of the Diagram: Communicating the Knowledge of the Heavens, the Earth and the Arcane, Final Part

• Scientific American Mind | 7 hours ago

### Brain's Glial Cells Spark Seizures

• Brainwaves | 7 hours ago

More »

## Latest from SA Blog Network

• ### Thrifty Thursday: A common dandelion, a common sunset, a common phone camera

Compound Eye | 4 hours ago
• ### Marine Protected Areas and Catalina Island: Conserve, Maintain and Enrich

Expeditions | 4 hours ago
• ### Once Upon A Time, The Catholic Church Decided That Beavers Were Fish

MIND
The Thoughtful Animal | 5 hours ago
• ### The Art and Science of the Diagram: Communicating the Knowledge of the Heavens, the Earth and the Arcane, Final Part

Guest Blog | 6 hours ago
• ### A Brief History of Mental Illness in Art

MIND
Brainwaves | 7 hours ago

## Science Jobs of the Week

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

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