Four Color Theorem/Historical Note

From ProofWiki
Jump to navigation Jump to search

Historical Note on the Four Color Theorem

The question of the minimal number of colors that are needed to color any arbitrary planar graph was first considered by Francis Guthrie in $1852$, when he was coloring a map of the counties of England.

He conjectured that the answer was $4$.

He published this conjecture in $1878$.

In $1879$, Alfred Bray Kempe published what he believed to be a proof, but in $1890$ it was shown by Percy John Heawood to be flawed.

In that same year, Heawood proved that $5$ colors were certainly enough.

In $1880$, another proof was published, but that was also shown to be flawed.

During the course of the century following, many developments in graph theory were made as a result of research into this problem.

Henry Ernest Dudeney, writing about it in a $1926$ publication, also drops the names of Augustus De Morgan, Arthur Cayley, Lothar Wilhelm Julius Heffter, Paul Wernicke, George David Birkhoff and Philip Franklin, and cites the work of Henry Roy Brahana before giving a (flawed) proof of his own.


What is now believed to be a sound proof of the Four Color Theorem was presented in $1976$ by Kenneth Ira Appel and Wolfgang Haken.

Their proof relies heavily on a computer program, set up to search through all the various cases.

Hence their proof does not easily conform to $\mathsf{Pr} \infty \mathsf{fWiki}$'s format.

Apart from this computer-based search, the proof is similar to that of the Five Color Theorem, a related but weaker result.


Some mathematicians distrust this proof because of its reliance on computers, and its consequent inability to be checked by humans.

This is part of a broader debate in mathematics over the increasing use of computers in proofs.


Historical Note by Henry Ernest Dudeney

For just about $50$ years various mathematicians, including De Morgan, Cayley, Kempe, Heawood, Heffter, Wernicke, Birkhoff, Franklin and many others have attempted to prove the truth of this theorem,
and in a long and learned article in the American Mathematical Monthly for July-August, $1923$, Professor Brahana, of the University of Illinois, states that "the problem is still unsolved."

Martin Gardner, in his $1968$ repackaging 536 Puzzles & Curious Problems, refutes Dudeney's claim to have proved it.

He goes on to advertise his own contribution in his $1966$ Martin Gardner's New Mathematical Diversions from Scientific American.


Sources