Short Features

Ken Appel and colleague Wolfang Haken proved tha any map can be drawn using just four colors in one of the most famous mathematical proofs. Photo by Doug Prince, UNH Photographic Services

Draw a map of New Hampshire, showing all 234 towns and cities. Grab a box of crayons and color each community, making sure none is the same color as any neighbor. What's the smallest number of crayons you can use?

The answer to this problem is well known: you will need only four crayons for that map. In fact, four colors are enough to distinguish every community from its neighbors on any map that has ever been made or ever could be made, no matter how convoluted or weird-looking.

How do we know that? Because 25 years ago, two mathematicians at the University of Illinois used a computer to tackle one of the most famous of all unsolved problems. In the process, they pioneered a new approach in mathematics.

"Most mathematicians, even as late as the 1970s, had no real interest in learning about computers. It was almost as if those of us who enjoyed playing with computers were doing something non-mathematical or suspect," recalls Ken Appel, who is now the chair of the mathematics department at UNH.

But in the early '70s, Appel and Wolfgang Haken decided to use a computer to prove the four-color theorem, which was developed centuries ago by mapmakers trying to minimize the number of inks they had to use. They found that four colors were always enough, but mathematicians, who tend to take ideas to extremes, wondered whether four would always be enough. Is it possible to draw a particularly squiggly map that needs a fifth color?

No one was ever able to produce such a map, but neither could anyone prove that it could not exist, even though many people gave it a shot. "This problem has always appealed to people's imaginations," Appel notes. "You could explain the four-color theorem to a class of high-school students, and immediately they'd begin working on it."

As is often the case in high-level mathematics, finding a solution required an oblique approach: Appel and Haken used the classic method of "proof by contradiction." First, they assumed the existence of a map that required more than four colors. Then, building on a century of earlier attempts, they developed formulas to describe possible maps in mathematical terms, using numbers and algorithms to express relationships between neighboring countries.

It is an elementary mathematical principle that if there are any maps that require five colors, then there must be such a map with a smallest number of countries. The crux of the proof is that there can be no such smallest map. The proof consisted of showing that every map must contain a configuration of countries that could not appear in a smallest map. As it turned out, in the original proof of the four-color theorem, the fact that almost 2,000 particular configurations could not appear in a smallest map needed to be verified by computer. No way to fully check these computations by unaided humans has yet been found.

In classic pragmatic-scientist fashion, the two piggybacked their work on an IBM 360 series machine-a mainframe computer originally dedicated to administrative tasks by a university vice president. With 64K of memory, it was more powerful than the machines usually available to them. Writing low-level assembly language, Appel and Haken started running calculations, tweaking their program, then doing more runs. It took the computer a total of 1,200 hours to go through all of the calculations. "Once we settled down on it, it was sort of like digging the Panama Canal-one shovelful at a time," Appel says.

The two mathematicians finished their work in July 1976 and published the results the following year in the Illinois Journal of Mathematics. Unfortunately, the calculations were so long and complicated that no human being could check them for errors. This was the first computer-dependent proof of an important theorem that mathematics had ever seen.

Reactions to the proof were mixed and, in some cases, extreme. Many mathematicians were complimentary, but some resented the fact that they had to take a computer's word on the solution to such a famous problem. It was not elegant, they said; it was not beautiful-and some feared it would taint the Queen of Sciences.

The argument raged loud and long-Scientific American even wrote a much-criticized article entitled "The Death of Proof"-but eventually, time and technology proved victorious over tradition. "I think if you talked to students today and said there were people who were very angry that computers were used in proof, they'd be puzzled as to why," says Appel. "By the 1980s, most grad students had, as kids, had some contact with computers, and they were comfortable with the idea of working with them."

Indeed, even the crustiest mathematicians now have hugely powerful systems at their disposal, but they're still doing pretty much what Appel and Haken did a quarter-century ago-following their instincts. "That's what one does as a mathematician: find an interesting problem, work at it and hope it pays off," Appel observes.

"We were lucky enough to come along just at a time when the tools were there," he adds. "As for me, I had one really bright idea, and that was to work with Haken, who is as sharp and hard-working as anybody I've ever met. The theory of collaboration is to find somebody smarter than you to work with. If there was a 'eureka moment' for me, that was it." ~

 Easy to print version