Four Color Map Theorem (March 28-31)

Francis Guthrie, a 21yearold mathematics student at University College in London, was mapping the counties of England in 1852 when he noticed that he only needed four colors for the map. He asked his younger brother, Frederick Guthrie, if this was true for any map. Frederick took the problem to his professor, Augustus de Morgan.

In 1878 Arthur Cayley presented this problem to the London Mathematical Society. He and various others tried to prove it over the next century. In 1976 Wolfgang Haker and Kenneth Appel of the Univeristy of Illinois proved the theorem using a computer. It took them four years to write the computer program for the Cray computer, which took 1200 hours to check 1476 configurations.

Some mathematicians are troubled by the proof by computer. They feel that a theorem so easy to understand should be able to be proved by hand. Anyone who can prove the theorem without the computer may win the Fields Medal, the math equivalent of the Nobel Peace Prize.

Now, color in the maps of the United States, Massachusetts, and each continent with no more than four colors. Remember no color can touch another color on a side, but may meet at a point.

The four color map theorem is one of the most famous and productive problems of graph theory which is the most important model of both natural and human-made structures. They can be used to model many types of relations and process dynamics in physical, biological and social systems. Many problems of practical interest can be represented by graphs.

In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. One practical example: The link structure of a website could be represented by a directed graph. The vertices are the web pages available at the website and a directed edge from page A to page B exists if and only if A contains a link to B. A similar approach can be taken to problems in travel (air traffic control), biology, computer chip design, and many other fields.