4 Colour Theorem

The four color theorem is a mathematical theorem that states that, given a map, no more than four colors are required to color the regions of the map, so that no 2 regions that are touching (share a common boundary) have the same color. This theorem was proven by Kenneth Appel and Wolfgang Haken in 1976, and is unique because it was the first major theorem to be proven using a computer. This proof was first proposed in 1852 by Francis Guthrie when he was coloring the counties of England and realized he did not need more than four colors to color the map. Either he or his brother published this theorem (you only need four colors to color a map) in The Athenaeum in 1854. Many people had tried to solve this and had failed, two notables who had tried were, Alfred Kempe (1879) and Peter Guthrie Tait (1880). Many mathematicians kept failing until around the 1960s – 1970s when German mathematician Heinrich Heesch developed a way to use computers to solve proofs. And by 1976 Kenneth Appel and Wolfgang Haken, at the University of Illinois had stated that they had proven the theorem.

They had used two technical concepts to prove that there was no map that had the smallest possible regions that required five colors. The two concepts were: 1. An unavoidable set contains regions such that every map must have at least one region from this collection. 2. A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, then the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, then the original map can also. This implies that if the original map cannot be colored with four colors the smaller map can’t either and so the original map is not minimal. What they had done was use mathematical rules and procedures to prove that a minimal counterexample to the four color conjecture could not exist. They had to check around 1900 reducible configurations which had to be checked one by one, this took over a thousand hours. This was then double checked by another computer program, it was then verified in over 400 pages of microfiche which had to be checked by hand.

Yet even in this proof, one mathematician had found a significant error, Appel and Haken were asked to explain this error. In 1989 they came out with a book that explained each error that had been found and how it was a result of a misinterpretation of some of the results. This is a very interesting theorem as it was the first to be done using a computer program and by exhaustion. Also as it relates to day to day life that not everyone notices or realizes. This theorem not only applies to finite graphs, but also infinite graphs that are drawn without crossings in the plane. It is a fairly new theorem and is very controversial as it was proved using a computer. It is controversial as many mathematicians consider computer based proofs are not actually “real” mathematical proofs as a computer can do steps that may not be verifiable by humans, and there can be many errors in the software and hardware of the program. Another statement is that mathematical proofs by computer are less elegant and provide no insight on new concepts.