What is the minimum number of colors that can be
used in coloring a map? That is, how can you color the map consisting of
any number of different regions or states, in a manner that no two adjacent
regions or states can have the same color? Two regions are called adjacent
only if they share a border segment, not just a point. Each region must be
contiguous, such as not containing exclaves.
The four color theorem (or four color map theorem)
states that given any plane separated into many regions, the regions may be
colored using no more than four colors in such a way that no two adjacent
regions sharing the same boundaries have the same color. This problem
dates back to 1852 when Francis Guthrie, while trying to color the map of
counties of England noticed that four colors sufficed.
It can easily be shown that using only three colors is inadequate. This can been
seen when one region is surrounded by three other regions (but not with an even
number of surrounding regions).
The four color theorem was the first major theorem actually proven using a
computer. However, the proof is yet not accepted by
all mathematicians because the proof is difficult to verify anually. The proof
also lack of mathematical elegance. One has to have faith in the accuracy of the
software and hardware executing the program used for the proof.
More Mathematical Recreations