27: How Many Crayons?

    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