Map Colors (was: Re: New <AREA> syntax proposal)

I haven't got a clue what this discussion is doing here, but...

Four colors is the maximum number of colors needed to color a "map" of any
number of regions (in the plane) of any shape in such a way that no regions
of the same color share a common border. ("Border" is defined as touching
at more than a single point. This was a very famous, long-standing problem
in topology. Actually, mapmakers had "known" more-or-less forever that they
only needed four colors. The problem was to *prove* that only four were needed
(or, obviously, to prove that there were "maps" that needed more than four).
I've forgotten when the problem was posed (Euler era? Before?) but it floated
around for three hundred years or so with billions of people doing incorrect
proofs (rather like the problem of squaring the circle, or Fermat's Last
Theorem). It was finally proven that four are enough by (I think) two
mathematicians in (I think) the late '60s or early '70s, who did it (if I
remember correctly) by proving that there are only some finite number of
(topologically) different maps (four or five hundred, I believe) and then
using a computer to exhaustively test all of them.

 > > >Four is the *minimum*, which is probably what you meant to write.
 > > Are you sure?  I mean, what about a map shaped like:
 > >
 > > ----------------------------
 > > |            |             |
 > > |            |-------------|
 > > |            |             |
 > > ----------------------------
 > 
 > Well, maps of unlimited size, I guess... ;-)
 > 
 > But what about a simple chess board?
 > 
 > No; I think 4 colors is the maximum EVER needed for ANY maps.

Received on Tuesday, 10 June 1997 22:55:41 UTC