would lose its charge.This effect was rediscovered by the famous AmericanThomas Edison early in1880.It was during1880 (only six years beforeFrederickdied) that Frederick wrote:Some thirty years ago, whenI was attendingProfessor De Morgan'sclass, my brother,Francis Guthrie, who had recently ceased to attendthen(and who is nowprofessor of mathematics at the SouthAfricanUniversity, Cape Town), showed me the fact that the greatest necnumber of colours to be used in colouring a map so as to avoid identitycolour in lineally contiguous districts is fofour.I should notbejustifiedafter this lapse of time, in trying to give his proof, but the critical dia-gram was as in the marginWith my brother's permission I submitted the theorem to ProfessorDe Morgan, who erpressed himnself very pleased with it; accepted it asnew; and, as I am informed by those who subsequently attended hisclasses, was in the habit of acknowledging where he had got his infor-mation.If I remember rightly, the proof which my brother gave did not seenaltogether satisfactory to himself; but Imust refer to him those interestedin the subject. ....Thefirst statementin print of theFour ColorProblem evidentlyoccurredinan anonymous review written in the 14 April 1860 issue of the literary journalAthenaeum. Although the author of the review was not identified, De Morgan wasquite clearly the writer. This review led to the Four Color Problem becoming knownin the United StateTheFourColorProblemcametotheattentionoftheAmericanmathematicianCharles Sanders Peirce (1839-1914),who found an example of a map drawn on atorus (a donut-shaped surface)that required six collors.(AswewillseeinChapter5)there isan exampleofamapdrawnonatorusthatrequiressevencolors.)Peirceerest in the Four Color Problem. In fact, he visited De Morganorein70,whobythat time wasexperiencingoorhealthIndeedeMorgandedthefllowing year.Not only hadDe Morganmadelttleprogresstowardsasolutionof the Four Color Problem at the time of his death, overall interest in this problemhad faded.While Peirce continued to attempt to solve the problem, De Morgan'sBritish acquaintancesappeared topaylittleattentiontotheproblem-withatleastone notableexception
5 would lose its charge. This effect was rediscovered by the famous American inventor Thomas Edison early in 1880. It was during 1880 (only six years before Frederick died) that Frederick wrote: Some thirty years ago, when I was attending Professor De Morgan’s class, my brother, Francis Guthrie, who had recently ceased to attend then (and who is now professor of mathematics at the South African University, Cape Town), showed me the fact that the greatest necessary number of colours to be used in colouring a map so as to avoid identity colour in lineally contiguous districts is four. I should not be justified, after this lapse of time, in trying to give his proof, but the critical diagram was as in the margin. . . .. .. ... ... ..... ...... ...... ......... ............ ................... ............ ........ ........ ....... ..... ..... ... .... .. .... .............................................................................................................................. . .. ... ...... ......... ............. ....... .... ...... .... .. . ........................................................ .................................. .............................. 1 4 2 3 With my brother’s permission I submitted the theorem to Professor De Morgan, who expressed himself very pleased with it; accepted it as new; and, as I am informed by those who subsequently attended his classes, was in the habit of acknowledging where he had got his information. If I remember rightly, the proof which my brother gave did not seem altogether satisfactory to himself; but I must refer to him those interested in the subject. . . .. The first statement in print of the Four Color Problem evidently occurred in an anonymous review written in the 14 April 1860 issue of the literary journal Athenaeum. Although the author of the review was not identified, De Morgan was quite clearly the writer. This review led to the Four Color Problem becoming known in the United States. The Four Color Problem came to the attention of the American mathematician Charles Sanders Peirce (1839–1914), who found an example of a map drawn on a torus (a donut-shaped surface) that required six colors. (As we will see in Chapter 5, there is an example of a map drawn on a torus that requires seven colors.) Peirce expressed great interest in the Four Color Problem. In fact, he visited De Morgan in 1870, who by that time was experiencing poor health. Indeed, De Morgan died the following year. Not only had De Morgan made little progress towards a solution of the Four Color Problem at the time of his death, overall interest in this problem had faded. While Peirce continued to attempt to solve the problem, De Morgan’s British acquaintances appeared to pay little attention to the problem – with at least one notable exception
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)
implying that M could be colored with four colors after all, thereby producing acontradictionCertainly,fthmapMonainsonsurounddbyweththree regions, a contradiction can be obtained in the same manner.8-人-8er0240(a) in M(c) in M(b) in MFigure 2: A region surrounded by three regions in a mapSuppose, however, that the map M contained no region surrounded by three orfewer regions but did contain a region R surrounded by four regions, say Ri, R2.R3,R4, as shown in Figure 3(a). If, once again, we shrink the region R to a point,producinga map M'with onelessregion,then weknow that M'can be coloredwith four colors.If two or three colors areused to color Ri,R2,R3,R4,then we canreturn to M and there is a color available for R. However, this technique does notwork if the regions Ri,R2, R3, Ry are colored with four distinct colors, as shownin Figure 3(b).Hredblueyellowgreen(b) in M'(a) in MFigure3:A region surrounded byfour regions in a maWhat we can do in this case,however.is todeterminewhether themap M' hasa chain of regions,beginning at R, and ending at R3,all of which are colored redor green. If no such chain exists, then the two colors of every red-green chain ofregions beginning at Ri can be interchanged. We can then return to the map M,where the color red is now available for R. That is, the map M can be colored withfourcolors, producing a contradictionBut what ifared-geen chain ofregionsbeginning at Ri and ending at Rs exists? (See Figure 4, where r,b, g,y denote thecolors red, blue, green, yellow.) Then interchanging the colors red and green ofersno benefit to us. However, in this case, there can be no blue-yellow chain of regions,beginning at R2 and ending at R4-Then the colors of every blue-yellow chain of
7 implying that M could be colored with four colors after all, thereby producing a contradiction. Certainly, if the map M contains a region surrounded by fewer than three regions, a contradiction can be obtained in the same manner. . .. ... ...... .......... .......... ......... ...... .... ... ................................................... . .. .... ..... ............... ....... ........... .... .. .. ................................................... . . . . . . . . . .. .............. .... . . . . . . . . . . . . . . . . . .. .................. .......... . . .. . .. ......... ........ .......... . . .. . .. ......... ........ ..................... R (a) (c) blue green red R3 green (b) in M′ in M in M R2 R1 yellow blue yellow Figure 2: A region surrounded by three regions in a map Suppose, however, that the map M contained no region surrounded by three or fewer regions but did contain a region R surrounded by four regions, say R1, R2, R3, R4, as shown in Figure 3(a). If, once again, we shrink the region R to a point, producing a map M′ with one less region, then we know that M′ can be colored with four colors. If two or three colors are used to color R1, R2, R3, R4, then we can return to M and there is a color available for R. However, this technique does not work if the regions R1, R2, R3, R4 are colored with four distinct colors, as shown in Figure 3(b). . .. .... ..... ............... ........ .......... .... .. .. ................................................... . .......... . .. ... .......... ......... ................................................................................................................................................................................. R R3 R1 green red R4 blue yellow R2 (a) in M (b) in M′ Figure 3: A region surrounded by four regions in a map What we can do in this case, however, is to determine whether the map M′ has a chain of regions, beginning at R1 and ending at R3, all of which are colored red or green. If no such chain exists, then the two colors of every red-green chain of regions beginning at R1 can be interchanged. We can then return to the map M, where the color red is now available for R. That is, the map M can be colored with four colors, producing a contradiction. But what if a red-green chain of regions beginning at R1 and ending at R3 exists? (See Figure 4, where r, b, g, y denote the colors red, blue, green, yellow.) Then interchanging the colors red and green offers no benefit to us. However, in this case, there can be no blue-yellow chain of regions, beginning at R2 and ending at R4. Then the colors of every blue-yellow chain of
CHAPTER 0.THE ORIGIN OF GRAPH COLORINGS8regions beginning at R2 can be interchanged. Returning to M, we see that the colorblue is now available for R, which once again says that M can be colored with fourcolors and produces a contradiction24Figure 4: A a red-s chain of regions from Ri to R3It is possible to show (as we will see in Chapter 5) that a map may contain noregion that is surrounded by four or fewer neighboring regions. Should this occurhowever, such a map must contain a region surrounded by exactly five neighboringregionsWe mentioned that James Joseph Sylvester worked with Arthur Cayley andserved as the second president of the London Mathematical Society.Sylvester, asuperb mathematician himself, was invited to join the mathematics faculty of thenewlyfounded JohnsHopkins University in Baltimore,Maryland in 1875.Includedamong his attempts to inspire more research at the university was his foundingin 1878 of the American Journal of Mathematics, of which he held the position ofeditor-in-chief.Whilethegoalof the journal was to serve American mathematiciansns were encouraged as well, including articles from Sylvester'sbmissiefriend CaylerAmongthosewhostudiedunderArthurCayleywasAlfredBrayKempe(18491922)espitehisgeatenthusasmfor mathmaticsKtook upacareer in thelegalprofesape was present at the meeting of the London MathematicalionKomrSociety in which Cayley had inquired about the status of the Four Color Problem.Kempe worked on the problem and obtained a solution in 1879. Indeed, on 17July 1879 a statement of Kempe's accomplishment appeared in the British journalNature, with the complete proof published in Volume 2 of Sylvester's AmericanJournal ofMathematics.Kempe's approachfor solvingtheFour ColorProblem essentiallyfollowed thetechnique described earlier. His technique involved locating a region R in a map Msuch that R is surrounded by five or fewer neighboring regions and showing that forg of M (minustheregionR)withfour colors.thereis a coloring of theevery colorinre map M with four colors. Such an argument would show that M could notbeaminimum counterexample.We sawhowsuch a proofwould proceed if R were
8 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS regions beginning at R2 can be interchanged. Returning to M, we see that the color blue is now available for R, which once again says that M can be colored with four colors and produces a contradiction. .................... ................... g r g r g g r R3 R1 R4 R2 b y g R r r ....... ..... .... ... .. ... .. .. .. ................. ............. ............................................................................................................. ............................. ..... . ..... ... .. ... .... ........... ...... ...... ............... ... .... .... .... .... .... .. ... ... ............... . ...... ..................... ........................ ............................................... ........................................ ............... ............ . ... .. ... ... .... ... ....... ... .. . ..... ...... ...... ....... ....... ......... ......... ........... ... .... ........... ...... ...... ..... ... .. .. ... ............................ .. .................. .. ... .. . . ...... .. .......................................................................... .. .. ... ..... .. .. ... ... ..... .. ... ... ... ... .... .... .... .... ...... ....... ......................... ......... ..... .. ... ... ....................................... .......................... ... .... .... ..... .... ...... ........ ........... ....... ..... .... ... ....... ....... ....... ..... ...... ...... ... ... .. .. .. ...... ............................................ .................. ....................................... .......... .................................... .. .. ... ... ... .. .. .. .. ... .. ..... ......... ......... ....... .............. ... ..... ..... ...... . ............... . .............. ................ ............ ... ..... ....... .... ... ... ... .... ... ..... ... .. .. ... .. ............... ...................................................................................... ............. ....... ..... .... ... .. .. .. .. .. .. ... .. .. ............. .. ............................................................. .. ........ ... ....... .. .......... .... ... ... ... ..... .. .. .. .. .. ................ .................................................................................. . ... .. .. .. .. .. . . . ... .. .. ..................................................... .......................................... . . .. .. ... ...... ... .. .. ........ ... .. ... ...... ........... ......... . ......................................... ............................................. ............................................................... Figure 4: A a red-green chain of regions from R1 to R3 It is possible to show (as we will see in Chapter 5) that a map may contain no region that is surrounded by four or fewer neighboring regions. Should this occur however, such a map must contain a region surrounded by exactly five neighboring regions. We mentioned that James Joseph Sylvester worked with Arthur Cayley and served as the second president of the London Mathematical Society. Sylvester, a superb mathematician himself, was invited to join the mathematics faculty of the newly founded Johns Hopkins University in Baltimore, Maryland in 1875. Included among his attempts to inspire more research at the university was his founding in 1878 of the American Journal of Mathematics, of which he held the position of editor-in-chief. While the goal of the journal was to serve American mathematicians, foreign submissions were encouraged as well, including articles from Sylvester’s friend Cayley. Among those who studied under Arthur Cayley was Alfred Bray Kempe (1849– 1922). Despite his great enthusiasm for mathematics, Kempe took up a career in the legal profession. Kempe was present at the meeting of the London Mathematical Society in which Cayley had inquired about the status of the Four Color Problem. Kempe worked on the problem and obtained a solution in 1879. Indeed, on 17 July 1879 a statement of Kempe’s accomplishment appeared in the British journal Nature, with the complete proof published in Volume 2 of Sylvester’s American Journal of Mathematics. Kempe’s approach for solving the Four Color Problem essentially followed the technique described earlier. His technique involved locating a region R in a map M such that R is surrounded by five or fewer neighboring regions and showing that for every coloring of M (minus the region R) with four colors, there is a coloring of the entire map M with four colors. Such an argument would show that M could not be a minimum counterexample. We saw how such a proof would proceed if R were
gions.Thisincludedlookingregforchainof regions whoses alternatebetweentwo colorsand theninterchangingthesecolors, if appropriate, to arrive at a coloring of the regions of M (minus R) withfoulhat the neighboring regions of R used at most three of these colorsTcolorssoand thereby leaving a color available for R. In fact, these chains of regions becameknown as Kempe chains, foritwas Kempewho originated this ideawas one case, however, that still needed to be resolved, namely the casen the map was surrounded by four or fewer neighboring regions.whereno regiorAs we noted, the map must then contain some region R surrounded by exactly fiveAt least three of the four colors must be used to color the fiveneighboring regions.neighboring regions of R. If only three colors are used to color these five regionsthen a color is available for R. Hence we are left with the single situation in whichall four colors are used to color thefiveneighboringregions surroundingR (seeFigure 5),where once agaib,g,y indicatethe colorsred,blue,green,yellowRFigure5:Thefinal case in Kempe'ssolution of theFour ColorProblemLet's seehow Kempe handled this final case.Among theregions adiacent to Ronlythe region R is colored yellow. Consider all theregions of the map M thatare colored either vellow or red and that. beginning at Ri. can be reached by analternating seguence of neighboring vellow and red regions.that is.by a vellow-redKempe chain. If the repion Ra (which is the neighboring region of R colored red)cannot be reached by a vellow-red Kempe chain.then the colors vellow and red canbe interchanged for all regions in M that can be reached by a yellow-red Kempechain beginning at Ri This results in a coloring of all regions in M (except R)eighborirecoloreddifferentlyand suchthateachneighboriWEn0region of Risolored red. blue.orgreen.Wecanthen colorRvellowtoarrriveatre map M. From this, we may asthat the region Rg can20or1moffne11be reached by a yellow-red Kempe chain beginning at Ri. (See Figure 6.Let's now look at the region Rs, which is colored green. We consider all regionsof M colored green or red and that, beginning at Rs, can be reached by a green-redKempe chain. If the region Rg cannot be reached by a green-red Kempe chain thatbegins at Rs, then the colors green and red can be interchanged for all regions in M
9 surrounded by four or fewer neighboring regions. This included looking for chains of regions whose colors alternate between two colors and then interchanging these colors, if appropriate, to arrive at a coloring of the regions of M (minus R) with four colors so that the neighboring regions of R used at most three of these colors and thereby leaving a color available for R. In fact, these chains of regions became known as Kempe chains, for it was Kempe who originated this idea. There was one case, however, that still needed to be resolved, namely the case where no region in the map was surrounded by four or fewer neighboring regions. As we noted, the map must then contain some region R surrounded by exactly five neighboring regions. At least three of the four colors must be used to color the five neighboring regions of R. If only three colors are used to color these five regions, then a color is available for R. Hence we are left with the single situation in which all four colors are used to color the five neighboring regions surrounding R (see Figure 5), where once again r, b, g, y indicate the colors red, blue, green, yellow. . ... ... ... ... . ..................................................................... ........ . . .. .. ............... ....... . . . . . . . . ............... .. ... ... ... .. .. ... ... .. ... .. ... ... ... . ................. . . . ..................................................................................... ................................. . . .. .. .. ... .... ........... .... .. .. . .... ..... ...... ..... ..................... .... ....... ........ .............. ........ ..... ... ... ... .... ..... .. .......... .. ... . . .. .. .. ... ... ....... ...... .......................... ............... . ... ..... ...... ..... . ........... ..... .. ................................. . . . ................................. . ..... ... .. ..... ... ... ....... .... ... ... . ... .. .. ... .................................................... ....................................................... .................................................... .......................................... .............. ........ ... .. .. ..... .. ............................................. ... ... .. ... .... ... ... ..... ........... ..... .... ... .. . .. ... ...... .......... ........ ... ........... . .......................................................... ............................................. ......... ......................... .. ... ... ... .. .. ... ... ..... .. .. ... .. ... .. .. . .... . . .. . ... . ............................ ...................... R g y b r b R4 R2 R5 R3 R1 Figure 5: The final case in Kempe’s solution of the Four Color Problem Let’s see how Kempe handled this final case. Among the regions adjacent to R, only the region R1 is colored yellow. Consider all the regions of the map M that are colored either yellow or red and that, beginning at R1, can be reached by an alternating sequence of neighboring yellow and red regions, that is, by a yellow-red Kempe chain. If the region R3 (which is the neighboring region of R colored red) cannot be reached by a yellow-red Kempe chain, then the colors yellow and red can be interchanged for all regions in M that can be reached by a yellow-red Kempe chain beginning at R1. This results in a coloring of all regions in M (except R) in which neighboring regions are colored differently and such that each neighboring region of R is colored red, blue, or green. We can then color R yellow to arrive at a 4-coloring of the entire map M. From this, we may assume that the region R3 can be reached by a yellow-red Kempe chain beginning at R1. (See Figure 6.) Let’s now look at the region R5, which is colored green. We consider all regions of M colored green or red and that, beginning at R5, can be reached by a green-red Kempe chain. If the region R3 cannot be reached by a green-red Kempe chain that begins at R5, then the colors green and red can be interchanged for all regions in M