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 were8 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