Did they finally solve the four-color map problem?

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? G.B.C., Van Nuys, California

Cecil replies:

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.

Cecil Adams

Send questions to Cecil via cecil@straightdope.com.