6CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSArthur Cayley (1821-1895) graduated from Trinity College, Cambridge in 1842and then received a fellowship from Cambridge, where he taught for fouraAfterwards,because of the limitations on hisfellowship,he was required to choosea profession. He chose law, but only as a means to make money while he couldcontinue to do mathematics. During 1849-1863, Cayley was a successful lawyerbut published some 250 research papers during this period, including many forwhich he is well known. One of these was his pioneeing paper on matrix algebra.Cayley was famous for his work on algebra.ichofichwasdone with theBritish mathematician James Joseph Sylvester (1814-1897),a former student ofDeMorgarappointed a professor of mathematics at Cambridge. TwoIn1863Cavleywasyears later, the London Mathematical Society was founded at University CollegeLondon and would serve as a model for the American Mathematical Society, foundedin1888.DeMorganbecame thefrst president ofthe LondonMathematical Societyfollowed by Sylvester and then Cayley. During a meeting of the Society on 13 June1878, Cayley raised a question about the Four Color Problem that brought renewedattention totheproblem:Has a solution been given of the statement that in colouring a map of acountry, divided into counties, only four distinct colours arerequired, sothat no two adjacent counties should be painted in the same colour?This question appeared in the Proceedings of the Society's meeting. In the April1879 issue of the Proceedings of the Royal Geographical Society, Cayley reported:Ihave not succeded in obtaining a general proof: and it is worth whileto erplain wherein the difficulty consists.Cayley observed that if a map with a certain number of regions has been coloredwith four colors and a new map is obtained by adding a new region, then thereis no guarantee that the new map can be colored with four colorswithout firstrecoloring the originalmap.This showed that any atempted proofofthe Four ColorConjecture using a proof by mathematical induction would not be straightforward.Another possible proof technique to try would be proof by contradiction.Applyingthis technique, we would assumethat theFour Color Conjecture is false.This wouldmean that there are some maps that cannot be colored with four colors. Among themaps that require five or more colors are those with a smallest number of regions.Any one of these maps constitutes a minimum counterexample. If it could be shownthat no minir counterexample could exist, then this would establish the truthof the Four Color Conjecture.r example, nominimum counterexample M could possibly contain aregionR surrounded by three regions Ri, R2, and Rs as shown in Figure 2(a). In thisse.we could shrinktheregionRtoapoint,producinganewmap M'with oneasless region. The map M' can then be colored with four colors, only three of whichare used to color Ri. Ra, and R3 as in Figure 2(b). Returning to the originalmap M, we see that there is now an available color for R as shown in Figure 2(c)6 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS Arthur Cayley (1821–1895) graduated from Trinity College, Cambridge in 1842 and then received a fellowship from Cambridge, where he taught for four years. Afterwards, because of the limitations on his fellowship, he was required to choose a profession. He chose law, but only as a means to make money while he could continue to do mathematics. During 1849–1863, Cayley was a successful lawyer but published some 250 research papers during this period, including many for which he is well known. One of these was his pioneering paper on matrix algebra. Cayley was famous for his work on algebra, much of which was done with the British mathematician James Joseph Sylvester (1814–1897), a former student of De Morgan. In 1863 Cayley was appointed a professor of mathematics at Cambridge. Two years later, the London Mathematical Society was founded at University College London and would serve as a model for the American Mathematical Society, founded in 1888. De Morgan became the first president of the London Mathematical Society, followed by Sylvester and then Cayley. During a meeting of the Society on 13 June 1878, Cayley raised a question about the Four Color Problem that brought renewed attention to the problem: Has a solution been given of the statement that in colouring a map of a country, divided into counties, only four distinct colours are required, so that no two adjacent counties should be painted in the same colour? This question appeared in the Proceedings of the Society’s meeting. In the April 1879 issue of the Proceedings of the Royal Geographical Society, Cayley reported: I have not succeeded in obtaining a general proof; and it is worth while to explain wherein the difficulty consists. Cayley observed that if a map with a certain number of regions has been colored with four colors and a new map is obtained by adding a new region, then there is no guarantee that the new map can be colored with four colors – without first recoloring the original map. This showed that any attempted proof of the Four Color Conjecture using a proof by mathematical induction would not be straightforward. Another possible proof technique to try would be proof by contradiction. Applying this technique, we would assume that the Four Color Conjecture is false. This would mean that there are some maps that cannot be colored with four colors. Among the maps that require five or more colors are those with a smallest number of regions. Any one of these maps constitutes a minimum counterexample. If it could be shown that no minimum counterexample could exist, then this would establish the truth of the Four Color Conjecture. For example, no minimum counterexample M could possibly contain a region R surrounded by three regions R1, R2, and R3 as shown in Figure 2(a). In this case, we could shrink the region R to a point, producing a new map M′ with one less region. The map M′ can then be colored with four colors, only three of which are used to color R1, R2, and R3 as in Figure 2(b). Returning to the original map M, we see that there is now an available color for R as shown in Figure 2(c)