12CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSThe colouring of abstract graphs is a generalization of the colouring ofmaps, and the study of the colouring of abstract graphs ..- opens a newchapter in the combinatorial part of mathematics.Gabriel Andrew Dirac (1951)For the present, however, we continue our discussion in terms of coloring theregionsofmapsKempe's proof of the theorem, which had become known as the Four ColorTheorem, was accepted both within the United States and England.Arthur Cayleyhad acceptedKeargument as a valid proof. This led to Kempe being electedasaFellowof theRoval Society in 1881The Four Color Theorem The regions of every map can be colored with four orfewer colors sothat everytwo adjacentreqions are colored differentlyy individuals who had become interested in the Four ColonongthProblem was Charles Lutwidge Dodgson (1832-1898), an Englishmannwithakeerinterest in mathematics and puzzles. Dodgson was better known, however, underhis pen-name Lewis Carroll and for his well-known books Alice's Adventures inWonderland and Through the Looking-Glass and What Alice Found There.Another well-known individual with mathematical interests, but whose primaryoccupation was not that of a mathematician, was Frederick Temple (1821-1902),Bishop of London and who would later become the Archbishop of Canterbury.LikeDodgson and others, Temple had a fondness for puzzleTempleshowedthat itas impossibleto have five mutually neighboring regions in any mapandfromthisconcluded that no map required five colors.Although Temple was correct aboutthe non-existence of five mutually neighboring regions in a map, his conclusion thatthis provided aproof of the Four Color Conjecturewas incorrectThere was historical precedence about thenon-existenceof five mutually adacent regions in any map. In 1840 the famous German mathematician AugustMobius (1790-1868)reportedly stated thefollog problem,which was proposedto him by the philologist Benjamin Weiske (1748-1809).Problem of Five PrincesThere was once a king with five sons. In his will, he stated that after hisdeath his kingdom should be divided into five regions in such a way thateach region should have a common boundary with the other four: Canthe terms of the will be satisfied?As we noted, the conditions of the king's will cannot be met. This problemillustrates Mobius' interest in topologubject of which Mobius was one of theearly pioneers. In a memoir written by Mobius and only discovered after his death,he discussed properties of one-sided surfaces, which became known as Mobius strips(even though it was determined that Johann Listing (1808-1882) had discoveredthese earlier).12 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS The colouring of abstract graphs is a generalization of the colouring of maps, and the study of the colouring of abstract graphs . . . opens a new chapter in the combinatorial part of mathematics. Gabriel Andrew Dirac (1951) For the present, however, we continue our discussion in terms of coloring the regions of maps. Kempe’s proof of the theorem, which had become known as the Four Color Theorem, was accepted both within the United States and England. Arthur Cayley had accepted Kempe’s argument as a valid proof. This led to Kempe being elected as a Fellow of the Royal Society in 1881. The Four Color Theorem The regions of every map can be colored with four or fewer colors so that every two adjacent regions are colored differently. Among the many individuals who had become interested in the Four Color Problem was Charles Lutwidge Dodgson (1832–1898), an Englishman with a keen interest in mathematics and puzzles. Dodgson was better known, however, under his pen-name Lewis Carroll and for his well-known books Alice’s Adventures in Wonderland and Through the Looking-Glass and What Alice Found There. Another well-known individual with mathematical interests, but whose primary occupation was not that of a mathematician, was Frederick Temple (1821–1902), Bishop of London and who would later become the Archbishop of Canterbury. Like Dodgson and others, Temple had a fondness for puzzles. Temple showed that it was impossible to have five mutually neighboring regions in any map and from this concluded that no map required five colors. Although Temple was correct about the non-existence of five mutually neighboring regions in a map, his conclusion that this provided a proof of the Four Color Conjecture was incorrect. There was historical precedence about the non-existence of five mutually ad￾jacent regions in any map. In 1840 the famous German mathematician August M¨obius (1790–1868) reportedly stated the following problem, which was proposed to him by the philologist Benjamin Weiske (1748–1809). Problem of Five Princes There was once a king with five sons. In his will, he stated that after his death his kingdom should be divided into five regions in such a way that each region should have a common boundary with the other four. Can the terms of the will be satisfied? As we noted, the conditions of the king’s will cannot be met. This problem illustrates M¨obius’ interest in topology, a subject of which M¨obius was one of the early pioneers. In a memoir written by M¨obius and only discovered after his death, he discussed properties of one-sided surfaces, which became known as M¨obius strips (even though it was determined that Johann Listing (1808–1882) had discovered these earlier)