Figure 1

Are four colors always enough to color any map so
that no two countries that share a border
(in more than single points) have the same color?
It is easy to show that you need at least
four colors, because Figure 1 shows a map with four
countries, each of which is touching the other. But
is four sufficient for any map?
Francis Guthrie made this conjecture in 1852, but
it remained unproven until 1976, when
Wolfgang Haken and Kenneth Appel showed that it
was true!
Also, quite interestingly, this proof required the
assistance of a computer to check 1,936 different cases
that every other case can be reduced to!
To date no one knows a quick short proof of this theorem.
Presentation Suggestions:
Draw a few pictures to illustrate why the problem is
difficult, and why (as some might ask)
it is not valid to try to
"check by example".
The Math Behind the Fact:
By the way, showing that five colors is sufficient
is relatively easy, and was proved in 1890. The ideas involved in
this and the four color theorem come from graph theory:
each map can be represented by a graph in which each country is a node,
and two nodes are connected by an edge if they share a common border.
The four color theorem is true for maps on a plane or
a sphere. The answer is different for geographic maps
on a torus; it turns out that
7 colors is necessary and sufficient then...
How to Cite this Page:
Su, Francis E., et al. "Four Color Theorem."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.
