The Four Color Theorem

By devantighe

  • The four-color conjecture is first made.

    The four-color conjecture is first made.
    Francis Guthrie noticed as few as four colors sufficed while coloring a county map of England, and hypothesized that this should be true of all maps in a 2D plane. After consulting Augustus de Morgan, Guthrie's Problem was sent forward to mathematicians hoping for a sufficient proof. The four color problem can be explained here. Link text

  • First attempted proof is published.

    Alfred Kempe's first attempted proof is published for the four-color conjecture.

  • Another incomplete graph theory proof is published.

    Peter Tait published an attempted proof for the conjecture using vertices and edges.

  • Fallacy is found in Kempe's algorithm.

    Fallacy is found in Kempe's algorithm.
    Percy Heawood of Durham University disproves Kempe's attempted proof using a figure with 18 faces.

  • Counterexample for Tait's proof is found.

    Julius Peterson's theorem showing a bridgeless 3-regular graph is factorable into three 1-factors disproves Tait's proof.

  • D-reducibility for unavoidable sets is discovered.

    Heinrich Heesch published a method of discharging in unavoidable sets that would later be a key piece in proving the conjecture.

  • Haken and Appel begin working together on the conjecture utilizing computer programming.

    Wolfgang Haken, having worked under Heesch for many years in attempting four-color proofs, partners with Kenneth Appel, a computer scientist, to begin working towards a computer-assisted proof.

  • A complete, computer-assisted proof is finally reached by Haken and Appel.

    A complete, computer-assisted proof is finally reached by Haken and Appel.
    Haken & Appel's algorithm for the four-color theorem is proven with 1800 iterations and 1000 hours of computing on an IBM 370-168 to print a 400-page detailed proof. Denial of this computer-generated proof sparked debate over technology's place in mathematics. The programming algorithm is taught in many computer science classes today. Link text

  • Simplified quadratic method was used to prove four color theorem more concisely.

    Robertson, Sanders, Seymour, and Thomas from Ohio State University and Georgia Institute of Technology implement a quadratic method to more concisely prove the four color theorem, still relying on the assistance from a computer to check all possible cases.