From: firstname.lastname@example.org Date: Tue, 10 Jun 1997 19:55:29 -0700 Message-Id: <199706110255.TAA17258@checfs1> To: email@example.com, firstname.lastname@example.org Subject: 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.