Map riddle + four colors + UI math department = celebration


Listen to this article

URBANA — Here's the task: Color a map of the United States so that no two adjacent states have the same color.

What's the least amount of colors you would need?

The answer to that question took mathematicians over a century to prove, with the assistance of a computer at the University of Illinois.

The Four Color Theorem, the first major theorem proved with help from a computer, was solved by UI mathematicians Wolfgang Haken and Kenneth Appel in 1976 and published in the Illinois Journal of Mathematics in 1977.

To mark the 40th annivesary of this achievement, the Department of Mathematics planned this weekend's "Four Color Fest," which continues today with an open house featuring hands-on activities for children and adults from 10 a.m. to noon and a concert at 7:30 p.m. All events are free and open to the public.

UI math Professor Jeremy Tyson said the four-color problem was first posed in 1852 in a letter from mathematician Francis Guthrie to his brother. He had been coloring maps of the counties of England and "realized he needed at least four colors to do it. Then he wondered whether every map could be colored using only four colors," Tyson said.

The problem gained widespread attention because it was easy to understand but "no one seemed to know the answer," he said.

In 1880, mathematician Alfred Kempe published a simple proof that was accepted until an error was discovered 11 years later.

Mathematicians began to analyze larger and larger maps and configurations to the point where it became impossible for a human to calculate by hand, with hundreds of thousands of possibilities, Tyson said.

"The problem stood until the advent of the computer age, when it became possible to write computer programs that could analyze the very large number of maps and configurations that had to be verified," he said.

Throughout the 1960s and '70s, mathematicians raced to finish the problem, which involved writing computer programs and then hand-checking the output, he said.

"And it was our team that scored the win," he said. "I would say it's one of the really signature achievements in this department that people think of when they think of Illinois and the Department of Mathematics."

Haken and his family are attending this week's festival. Haken's children helped him check the algorithms in 1976 when they were teenagers, Tyson said.

Also on hand will be Appel's son, Princeton computer-science Professor Andrew Appel, whose lecture Friday explained how some of the computer programs and algorithms used to prove the Four Color Theorem turned out to be useful for other computer-science problems.

At today's Open House, children can don colorful ponchos and fill in a huge map drawn on the floor, navigate a maze, color maps or take part in other hands-on activities. It's scheduled for 10 a.m. to noon in the ballroom at the Alice Campbell Alumni Center, 601 S. Lincoln Ave., U.

The concert, "A Portrait in Four Colors," is scheduled for 7:30 p.m. in the Music Building Auditorium, 1114 W. Nevada St., U. The featured instrument will be the Haken Continuum, invented by Wolfgang Haken's son, UI engineering Professor Lippold Haken. It will be played by internationally renowned musician Rob Schwimmer of New York, joined by Rudolf Haken on the electric viola and other musicians.

The program will include classical, jazz, blues and rock genres as well as dance and original compositions.


Julie Wurth is a reporter covering the University of Illinois at The News-Gazette. Her email is, and you can follow her on Twitter (@jawurth).