Suppose your child is filling in the pictures in a coloring book,

following the commonsense rule that any two areas touching each other

must be different colors. How many different colors do you need? Of

course you can use more colors than needed, but the question we are

interested in is the minimum number of colors that will be required.

Also, we are considering regions 'touching' only if they share a

nonzero portion of their border: areas touching at a single point do

not count. Otherwise, by drawing something like a pizza with lots of

slices that touch in the center, you could make figures requiring any

arbitrary number of colors. This problem was first formulated by a

mapmaker in 1852, trying to color a map of the counties of England.

And here is the answer: Four. Yes, *any* planar figure separated

into regions can be filled in using no more than four colors. This is

known as the "Four-Color Theorem". If only all answers in mathematics

could be this simple.

Basically, the theorem says that you can't draw a map in which

five contiguous countries all share borders with each other, which

would require five colors to fill in. If you grab a pencil and start

drawing shapes on paper, you will quickly come to believe the truth of

this theorem. Pause the podcast and try it! Drawing two shapes that

touch, and thus require two colors, is easy, and adding a third that

touches them both is also simple. Then, when you add a fourth, you

will find that at least one of your original regions is completely

surrounded. There is no way to make a fifth that touches the

original four, and you are hosed.

Because the truth of the theorem seems obvious once you play with

some pictures, it is tempting to create not-quite-valid "proofs" of

the theorem. In the late 1800's, two different mathematicians

published proofs of the Four-Color Theorem, and each was thought to be

valid-- until, 11 years later, both were debunked. The less stringent

"Five Color Theorem", which says that five colors will be sufficient,

was proven in 1890 by Percy Heawood, a British mathematician who

devoted his career to studying this theorem.

The four color version was finally proven in 1976, by Kenneth

Appel and Wolfgang Haken at the University of Wisconsin. The proof was

actually very controversial, because it was partially done by

computer: a program that ran for hundreds of hours analyzed 1,476

possible configurations as an important part of the proof. So, was it

really proven? It's tempting to be skeptical, since all of us who

have used Microsoft software know how easy it is to mess up when

writing a computer program. No mathematician has actually verified

what was done, step by step. But I would tend to say yes, this proof

probably is valid: after all, it's not necessarily much harder to

find an error in a computer program than by hand tracing the

multi-hundred-page proofs of many other major modern theorems.

As an interesting footnote, after all this effort, it

turns out that the theorem doesn't really have much practical

application in real-life cartography! One issue is that regions on a

map are not always contiguous, so violate a basic assumption of the

theorem. A simple example is lakes and rivers: typically all bodies

of water are blue, but they are not all connected to each other. So

four countries that mutually touch and all contain lakes will actually

require five colors. Another simpler reason is that mapmakers tend to

want to create visually pleasing images, and modern printing

techniques allow millions of possible colors, so why would they need

to minimize them? Sometimes what is interesting to a mathematician

just seems silly to an artist. And vice versa.

And this has been your math mutation for today.

Four Color Theorem on
Wikipedia

## No comments:

## Post a Comment