A Straight Dope Classic from Cecil's Storehouse of Human Knowledge

Did they finally solve the four-color map problem?

March 9, 1984

Dear Cecil:

I heard that the four-color map problem was solved recently ... by a computer! What's the straight dope on this, Cecil? Is this only a "limited" solution?

Dear G.:

I don't know that I would call 1976 "recently," but yes, the four-color map problem was solved (more or less) using a computer by two prairie geniuses at the University of Illinois at Champaign-Urbana, Wolfgang Haken and Kenneth Appel.

The four-color map problem, as all mathematically hip personages know, is to determine whether there is any map that requires the use of more than four different colors if you want to avoid having adjacent regions be the same color. A matter of no great consequence, you might think, but this is the sort of thing that fascinates math aficionados--in this case for well over a century. Haken and Appel proved that (as was widely suspected) four colors are all you ever need.

Cecil would be pleased to reproduce H&A's proof here, except that it took 1,200 computer hours and a zillion cubic yards of printout paper to do, so you're just going to have to take my word for it. Basically what the computer did was check out all the possible map combinations by trial and error.

There are those who complain that this process does not constitute a mathematical proof, as that term is usually understood, but rather falls more into the category of an experiment, understandably something of a novelty in the field of abstract mathematics. Some suggest that a simpler and more elegant proof may yet be found. But most experts regard the H&A proof as quite sufficient in the meantime.

Related Posts with Thumbnails

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope! Your direct line to thou- sands of the smartest, hippest people on the planet, plus a few total dipsticks.

Publishers - interested in subscribing to the Straight Dope? Write to: sdsubscriptions@chicagoreader.com.

Copyright © 2015 Sun-Times Media, LLC.