The Four Color Problem and its connection to South African Flora

In the 1850's Francis Guthrie was the first mathematician to formulate the Four Color Problem . He asked whether it is possible to color any map with four or fewer colors so that adjacent regions (those that share a common boundary) are colored differently. At the time when he posed the problem, he was a student at University College in London.

He attempted to prove that the counties of any map could be colored in this map with four colors.

However, he was not entirely satisfied with his proof, so he mentioned his problem to his brother Frederick, who, in turn, mentioned it to his instructor, the famous Augustus De Morgan (after whom De Morgan's Laws of set theory are named). In a letter dated October 23, 1852, De Morgan mentioned the problem to Sir William Rowan Hamilton (for whom hamiltonian graphs are named). In his response, Hamilton, perhaps displaying his insight into the difficulty of mathematical problems, replied to De Morgan that he did not plan to consider this problem in the near future. Evidently, De Morgan spoke often of this problem with other mathematicians. Indeed, De Morgan is credited with writing an anonymous article in the April 14, 1860, issue of the journal Athenaeum in which he discusses the Four Colour Problem. This is the first known published reference to the problem.

By the 1860's, the problem had crossed the Atlantic Ocean and piqued the interest of the American philosopher C. S. Pierce. Awareness of the Four Color Problem increased substantially when, on June 13, 1878, the renowned mathematician Arthur Cayley asked if the problem had been solved. Shortly afterwards, Cayley [2] published a paper on the Four Color Problem, in which he postulated why this problem appears to be so difficult.

The next major news came from an announcement in the July 17, 1879, issue of the journal Nature that the Four Color Problem had been solved in the affirmative by the British barrister Alfred Bray Kempe. His solution of the problem appeared in a paper [4] published in an 1879 issue of the American Journal of Mathematics. Thus, Kempe's paper contained the first published "proof" that the regions of any plane graph can be colored with four colors so that adjacent regions are colored differently.

For the decade following the publication of Kempe's paper, the Four Color Problem was considered as solved. For his accomplishment, Kempe was made a Fellow of the Royal Society. Kempe presented refinements of his proof, and P.G. Tait of the University of Edinburgh described yet another "proof". Lewis Carroll, author of the famous children's story "Alice in Wonderland", created a game for two players in which one player designed a map for his or her opponent to four-color. In 1889, the Bishop of London (Frederick Temple), later Archbishop of Canterbury, published his own solution of the Four Color Problem in the Journal of Education.

The case was not closed, however. In 1890, Percy John Heawood stated that he had discovered an error in Kempe's proof-an error so serious that he was unable to repair it. In his paper [3], Heawood gave an example of a map which, although it could easily be 4-colored, showed that Kempe's proof technique did not work in general. However, Heawood was able to use Kempe's technique to prove that every map could be 5-colored.

On June 21, 1976, Kenneth Appel and Wolfgang Haken [1] of the University of Illinois announced that, with the aid of John Koch, they had solved the Four Color Problem. It was not surprising that this claim met with much skepticism, especially since the proposed solution had required hundreds of hours of computer calculations. However, their solution has withstood scrutiny and the test of time.

Francis Guthrie eventually moved to South Africa where he became a mathematics professor at the South African College in Cape Town (which later became the University of Cape Town.) He was an avid amateur botanist-a worthwhile hobby in the Southwestern Cape with its wealth of indigenous flora. Three rare species of flowers were named after Guthrie. All three grow in the Bredarsdorp area

1. Cyrtanthus guthrieae
(also called Amaryllidaceae)
These begin blooming in March
before their leaves appear
2. Gladiolous guthriei (also called Iridaceae)
These bloom in winter (June-July).
They have a strong scent and occur
in the Pearly Beach area.
3. Homoglossum guthriei
These bloom in the spring
(August-September). They
have no scent and are
extremely rare.

References

  1. K. Appel and W. Haken, The solution of the Four-Color Map Problem. Sci. Amer. 237 (1977), 108-121.
  2. A. Cayley, On the colourings of maps. Proc. Royal Geog. Soc. 1 (1879), 259-261.
  3. P. J. Heawood, Map-colour theorem. Quart. J. Math. 24 (1890), 332-339.
  4. K. O. May, The origin of the four-color conjecture. Isis. 56 (1965), 346-348.