Reducible Configurations and So On: The Final Years of the Four Color Theorem

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Jeremy Preston Magee (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site:
Paul Duvall

Abstract: The Four Color Theorem is in a set of mathematical questions that are very simple to state but amazingly complex to answer. It goes as follows, "given any map, are any more than 4 colors required to color the map in such a way that no two areas which share a border also share a color?"(2). It was thought to be proven by Alfred Kempe for nearly a decade using a unique but unsuccessful process later referred to as Kempe chains. It wasn't until 1913, with George Birkhoff's treatment of reducibility, was true progress from the "proof" of Kempe to be made. From here, Heinrich Heesch explored reducibility with an improvement on the established A, B, and C-reducibilities, finding something algorithmically sound in D-reducibility and his subsequent discharging methods. Then Karl Durre introduced the first, somewhat rudimentary, computer program of D-reducibility. From here the extensive use of the super computers of the era helped seal the fate of the long unfinished theorem, with Wolfgang Haken and Kenneth Appel at the helm. We seek to examine the history of this theorem from the proof of Kempe to the utilization of reducible configurations and discharging methods of Durre and Heesch and into the eventual proof of the theorem itself.

Additional Information

Language: English
Date: 2008
Four, Color, Reducible
Four-color problem $x History.
Map-coloring problem $x History.
Topological graph theory.

Email this document to