The History of the Four Color Problem

# The History of the Four Color Map Problem

### What is the largest possible chromatic number?

This question has puzzled mathaticians
for a very long time. Hopefully you didn't spend too much time looking for a graph with
a chromatic number of 5 since it has now been proved that any
graph will have a chromatic number of at most 4. This is called
the **Four Color Problem**.

Map makers have known for a very long time that it only takes
four colors to color a map so that none of the borders have the same
color. In 1852, Francis Guthrie became intrigued by this and wanted
to prove it. He passed the problem along to his brother, who then
asked his profesor, DeMorgan. Over time, there were many conjectures
and proofs offered to show that this was true. Even mathematicians
make errors though and many flaws were found. In 1976 Appel and Heken
developed a proof that has so far stood the test of time. The proof
uses a computer and takes up a whole book. Heken has taken bets on the
validity of their proof, so far he has won.

## For more historical information you may visit these
websites:

Next: Graph Theory: Map Coloring

Back: Graph Coloring: Chromatic
Number