The Four Color Theorem Essay Research

The Four Color Theorem Essay, Research Paper

The Four Color Theorem Throughout history, mapmakers have perfected the art of making maps that allow for viewers to differentiate between distinct regions, such as countries or states. With any mapmakers given knowledge and practice, it has become known that if you plan well enough, you will never need more than four colors to color the maps that you make. The basic rule for coloring a map is that no two regions that share a boundary can be the same color, this only due to the indistinctness a map would from a distance. However, It is permissible for two regions that only meet at a single point to be colored the same color. Mapmakers are not mathematicians, so the theory that only four colors would be necessary for all maps gained acceptance in the map-making community over the years because not only did any one ever stumbled upon a map that required the use of five colors, but no one had also ever bothered to prove this assumption through a theorem solved by proofs. When mathematicians caught word of this basic yet interesting assumption, they began doing the things that mathematicians do best, asking questions. These questions would eventually trigger an in depth study of this baffling assumption.The Four Color Conjecture first seems to have been made by Francis Guthrie, a student at University College London where he studied under De Morgan. After graduating from London he studied law and by this time his brother, Frederick Guthrie, also had become a student of De Morgan. Francis Guthrie showed his brother some results he had been trying to prove about the coloring of maps and asked Frederick to ask De Morgan about them. De Morgan was unable to give an answer. Yet, before continuing with the history of the Four Color Conjecture, it is important to understand the details of Francis Guthrie, his life, studies, and contributions. After practicing as Boocock 2a barrister, Guthrie went to South Africa in 1861 as a Professor of Mathematics. He published a few mathematical papers and became interested in botany. Yet still intrigued by the initial questions and ideas that Guthrie had presented to his old professor, De Morgan continued seeking a solution to Guthrie’s problem and several mathematicians contributed their creative genius with hopes of finding a solution. Charles Peirce attempted to prove the Conjecture in the 1860’s and he was to retain a lifelong interest in the problem. Cayley also learnt of the problem from De Morgan and in June of 1878 he asked a question to the London Mathematical Society asking if the Four Color Conjecture had been solved. Shortly afterwards Cayley sent a paper on the coloring of maps to the Royal Geographical Society and it was published in 1879. The paper explains where the difficulties lie in attempting to prove the Conjecture. On July 17, 1879 Alfred Bray Kempe announced that he had a proof of the Four Color Conjecture. Kempe was a London barrister who had studied mathematics under Cayley at Cambridge and devoted some of his time to mathematics throughout his life. At Cayley’s suggestion, Kempe submitted his theorem to the American Journal of Mathematics where itwas published in 1879. In this paper, Kempe presented an argument which has now become to be known as the method of Kempe chains and, shortly after, received great acclaim for his proof. He was later elected a Fellow of the Royal Society and served as its treasurer for many years and was eventually knighted in 1912. He later published two improved versions of his proof, the second of which aroused the interest of P G Tait, the Professor of Natural Philosophy at Edinburgh. Tait addressed the Royal Society of Edinburgh on the subject and published two papers on what is now known as the Four Color Theorem. The Four Color Theorem returned to being the Four Color Conjecture in 1890. Percy John Heawood, a lecturer at Durham England, published a paper called Map coloring theorem. Boocock 3In it he states that his aim is rather destructive than constructive, for it will be shown that there is a defect in the now apparently recognized proof. Although Heawood showed that Kempe’s proof was wrong, he did prove that every map can be 5-colored in this paper. Kempe reported the error to the London Mathematical Society himself and said he could not correct the mistake in his proof. In 1896, de la Vall e Poussin also pointed out the error in Kempe’s paper, apparently unaware of Heawood’s work. Heawood was to work throughout his life on map coloring, work which spanned nearly 60 years. He successfully investigated the number of colors needed for maps on other surfaces and gave what is known as the Heawood estimate for the necessary number in terms of the Euler characteristic of the surface. Heawood was to make further contributions to the Four Color Conjecture. In 1898 he proved that if the number of edges around each region is divisible by 3 then the regions are 4-colourable. He then wrote many papers generalizing this result.

Now, to understand the later work applicable to the theorem, there are other concepts that must be defined. Clearly, a graph can be constructed from any map with the regions being represented by the vertices and two vertices being joined by an edge if the regions corresponding to the vertices are adjacent. The resulting graph is planar, that is can be drawn in the plane without any edges crossing. The Four Color Conjecture now asks