In 1852, Francis Guthrie, a South African mathematician, experimented with coloring the counties of England while he was in school at University College in London. Guthrie proposed that four colors were sufficient to fill in all of the regions of a map without any two adjacent regions having the same color. Guthrie’s proposition became known as the Four Color Problem. This seemingly simple proposition perplexed the minds of mathematicians for over a century. Mathematicians made several failed attempts at both proofs and counterexamples until finally, in 1976, Kenneth Appel and Wolfgang Haken proved the statement using a computer. Their proof, however, was not accepted by ...view middle of the document...
Historical Attempts at Proof:
As stated in the introduction, Guthrie proposed the Four Color Problem in 1852. Soon after this time, Guthrie’s brother passed the problem on to his math instructor, de Morgan. After considerable work and collaboration, de Morgan was unable to reach a valid proof that four colors are sufficient to color any map.
The first attempt at a complete proof of Guthrie’s proposition came in 1879 when Alfred Kempe completed his work based on the concept of reduction. He found that any map can be reduced (eliminate one or more regions) through a specific algorithm until the reduced map resembled a map that could be colored with only five colors. All of the steps in his algorithm for reduction did not cause the final map to require less colors than the original map. The following are some of his reduction techniques :
1. If a region is entirely surrounded by another (ex. Lesotho, which is surrounded by South Africa), then the inner region may be combined with the outer one. This reduction does not reduce the total number of colors needed because the color of the inner region must simply be different than the combined region.
2. At a corner with four or more regions coming to a single point, at least two of these regions will not share a common border. Therefore, these regions can be the same color, and hence, they are combined. (ex. This reduction can be applied at the Four Corners Point in the southwest United States to combine Utah and New Mexico.)
3. If a region is located on the border of two other regions such that it only touches those two other regions (ex. South Carolina between North Carolina and Georgia [ignoring oceanic borders]), then the middle region can be combined with either one of the other two regions. In this case, the middle region would need to be a different color than either of the two bordering regions which would only require three colors, and the color of the two regions bordering other regions would not be affected.
4. The same principle from case (3) can be applied to a region that is located on the borders of three other regions such that it only touches those three regions (ex. Delaware, which is surrounded by Maryland, Pennsylvania, and New Jersey [assuming the Delaware River/Bay is a border with New Jersey]). If the reduced map can be colored with only four colors, then the original map can as well since the outer regions’ borders with other regions are not affected, and the inner region that was combined can be colored with the fourth color, different than the three surrounding regions.
5. Following the same logic in cases (3) and (4), a region that is bounded in all directions by four other regions (ex. Alabama, which is surrounded by Georgia, Florida, Mississippi, and Tennessee) can be combined with one of the outer regions without affecting the original coloring if five colors are available.
By use of these reduction techniques, Kempe did successfully prove a “Five...