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 if the vertices of the graph can be colored with 4 colors so that no two adjacent vertices are the same color. From the graph a triangulation can be obtained by adding edges to divide any non-triangular face into triangles. A configuration is part of a triangulation contained within a circuit. An unavoidable set is a set of configurations with the property that any triangulation must contain one of the configurations in the set. A configuration is reducible if it cannot be contained in a triangulation of the smallest graph which cannot be 4-colored. The search for avoidable sets began in 1904 with work of Weinicke. Renewed interest in the states was due to Veblen who published a paper in 1912 on the Four Color Conjecture Boocock 4generalizing Heawood’s work. Further work by G D Birkhoff introduced the concept of reducibility upon which most later work rested. Franklin, in 1922, published further examples of unavoidable sets and used Birkhoff’s idea of reducibility to prove, among other results, that any map with 25 regions can be 4-colorred. The number of regions which resulted in a 4-colorable map was slowly increased. Reynolds increased it to 27 in 1926, Winn to 35 in 1940, Ore and Stemple to 39 in 1970 and Mayer to 95 in 1976. Yet, the final ideas necessary for the solution of the Four Color Conjecture had been introduced before these last two results. Heesch, in 1969, introduced the method of discharging which consists of assigning to a vertex of degree i the charge 6-i. Now from Euler’s formula, one can deduce that the sum of the charges over all the vertices must be 12. A given set S ofconfigurations can be proved unavoidable if for a triangulation T which does not contain a configuration in S we can redistribute the charges, without changing the total charge, so that no vertex ends up with a positive charge. Heesch thought that the Four Color Conjecture could be solved by considering a set of around 8900 configurations. There were difficulties with his approach since some of his configurations had a boundary of up to 18 edges and could not be tested for reducibility. The tests for reducibility used Kempe chain arguments but some configurations had obstacles to prevent reduction. In 1976, the Four Color Conjecture officially became known as the Four Color Theorem for the second, and last, time. The proof was achieved by Appel and Haken, basing their methods on reducibility using Kempe chains. They carried through the ideas of Heesch and, eventually, they constructed an unavoidable set with around 1500 configurations. They managed to keep the boundary ring size down to 14 making computations easier that for the Heesch case. There was a long period where they essentially used trial and error together with intuition to modify their unavoidable set and their discharging procedure. Appel and Haken used Boocock 51200 hours of computer time to work through the details of the final proof. Koch assisted Appel and Haken with the computer calculations. The Four Color Theorem was the first major theorem to be proved using a computer, having a proof that could not be verified directly by other mathematicians. Despite some worries about this initially, independent verification soon convinced everyone that the Four Color Theorem had finally been proved. The proof shows that if approximately 1,936 basic forms of maps can be colored with four colors, then any given map can be colored with four colors. A computer program colored these basic forms. So far nobody has been able to prove it without using a computer. In principle, it is possible to copy the computer proof by hand computations. The known proofs work by way of contradiction. The basic thrust of the proof is to assume that there are counterexamples, thus there must be minimal counterexamples in the sense that any subset of the graphic is four colorable. Then it is shown that all such minimal counterexamples must contain a subgraph from a set basic configurations. But it turns out that any one of those basic counterexamples can be replaced by something smaller, while preserving the need for five colors. The number of basic forms, or configurations has been reduced to 633. A recent simplification of the Four Color Theorem proof, by Robertson, Sanders, Seymour and Thomas, has removed the cloud of doubt hanging over the complex original proof of Appel and Haken. The programs can now be obtained by ftp and easily checked over for correctness. Also the paper part of the proof is easier to verify. This new proof, if correct, should dispel all reasonable criticisms of the validity of the proof of this theorem.