At least four colors are required to solve the general

Chapter 6, Problem 81

(choose chapter or problem)

At least four colors are required to solve the general map-coloring problem (see Exercise 78). Because no one could produce a map requiring more than four colors, the conjecture was formulated that four colors are indeed sufficient. This conjecture became known as the four-color problem. It was first proposed to the mathematician Augustus De Morgan by one of his students in 1852, and it subsequently received much attention. It remained unproved, however, for over a hundred years. In 1976 two mathematicians at the University of Illinois, Wolfgang Haken and Kenneth Appel, used a computer to work through a large number of cases in a proof by contradiction, thus verifying the four-color conjecture. The dual graph for a map (see Exercise 79), by the way it is constructed, will always be simple, connected, and planar. In addition, any simple, connected, planar graph can be viewed as the dual graph of a map. Restate the four-color conjecture in terms of the chromatic number (see Exercise 80) of a graph.