In 1852 a South African mathematician, Francis Guthrie, was coloring a map of the counties of England and suspected that four colors would suffice to color any map so that two counties that border have different colors.
Guthrie’s question was considered by various mathematicians of the time, and two “proofs” that four colors sufficed were announced, by Alfred Kempe in 1879 and by Peter Tait a year later. These proofs lasted eleven years before each was found to have fatal flaws, leaving the problem open for nearly a century more.
In 1976 Kenneth Appel and Wolfgang Haken finally gave a proof that four colors suffice, using a controversial technique. Their proof required using a computer to verify all the cases needed to make their argument work.
Traditional mathematicians didn’t trust a proof not completely checked by a human mind, but many decades later no mistakes have been found in the Appel-Haken proof, and few today doubt that every map can be four-colored.
Is four the limit? Can any map be colored with three colors? No. Consider Nevada and its neighbors.
There are computationally efficient algorithms for finding how to
color a map with four colors based on proofs of the four-color theorem.
Tags:
Other