18CHAPTER0.THEORIGINOFGRAPHCOLORINGStwelve pentagons (5-gons).In fact, there is a map containing exactly twelve regions,each of which is a pentagon. Such a map is shown in Figure 15, where one of theregions is the “exterior region". Since this map can be colored with four colors, anycounterexample to the Four Color Conjecture must contain at least thirteen regions.Aifred Errera proved that no counterexample could consist only of pentagons andhexagons (6-gons).Figure15:AcubicmapwithtwelvepentagonsA reducible configuration is any configuration of regions that cannot occur ina minimum counterexampleof theFour Color Conjecture.Manymathematicianswho attempted to solve theFour Color Problem attempted to do so by trying tofind an unavoidable set S of reducible configurations.Since S is unavoidable,thismeans that every cubicmapmust containat least oneconfiguration in S.Becauseeach configuration in S is reducible, this means that it cannot occur in a minimumcounterexample. Essentially then, a proof of the Four Color Conjecture by thisapproachwouldbeaproofbyexampleresultinginanumberofmnmintercases (one case for each coonfiguration in theunavoidableset S)where each caseleadstoa contradiction (that is.each configuration isshowntobereducible)navoidable set shown inFigure14thatSince the onlyconfiguration in theucould not be shown to be reducible was the pentagon, this suggested searching formore complex configurations that must also be part of an unavoidable set withthe hope that these more complicated configurations could somehow be shown tobe reducible.For example, in 1903 Paul Wernicke proved that every cubic mapcontaining no k-gon where k<5must either contain two adjacentpentagons ortwo adjacent regions, one of which is a pentagon and the other a hexagon (seeChapter 5).That is, the troublesome case of a cubic map containing a pentagoncould be eliminated andreplaced bytwo different cases.Finding new, large unavoidable sets of configurations was not a problem. Find-ing reducible configurations was.In 1913 the distinguished mathematician GeorgeDavid Birkhoff (1884-1944)published a paper called The reducibility of maps inwhich he considered rings of regions for which there were regions interior to as wellas exterior to the ring. Since the map was a minimum counterexample,the ring to-gether with the interior regions and the ring together with the exterior regions couldboth be colored with four colors. If two 4-colorings could be chosen so that theymatch along the ring, then there is a 4-coloring of the entire map. Since this canalways be done if the ring consists of three regions, rings of three regions can neverappear in a minimum counterexample.Birkhoff proved that rings of four regionsalso cannot appear in a minimum counterexample. In addition, he was successful18 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS twelve pentagons (5-gons). In fact, there is a map containing exactly twelve regions, each of which is a pentagon. Such a map is shown in Figure 15, where one of the regions is the “exterior region”. Since this map can be colored with four colors, any counterexample to the Four Color Conjecture must contain at least thirteen regions. Alfred Errera proved that no counterexample could consist only of pentagons and hexagons (6-gons). . . ... ....... ........... ........ ..... ... .. ........................................ . . .. ... .... ...... ....... ................... ............ ............ ...... .... ... .... . ................................................................................ . . .. .. ... .... .... ..... ....... ........ ............. ................... ........ ....... ......... ....... ...... .... .... ... .. .. . ....................................................................................................................... . .............................. ............................... .. . . ... ... . .......... ............................ .................... . .. . .. . . . Figure 15: A cubic map with twelve pentagons A reducible configuration is any configuration of regions that cannot occur in a minimum counterexample of the Four Color Conjecture. Many mathematicians who attempted to solve the Four Color Problem attempted to do so by trying to find an unavoidable set S of reducible configurations. Since S is unavoidable, this means that every cubic map must contain at least one configuration in S. Because each configuration in S is reducible, this means that it cannot occur in a minimum counterexample. Essentially then, a proof of the Four Color Conjecture by this approach would be a proof by minimum counterexample resulting in a number of cases (one case for each configuration in the unavoidable set S) where each case leads to a contradiction (that is, each configuration is shown to be reducible). Since the only configuration in the unavoidable set shown in Figure 14 that could not be shown to be reducible was the pentagon, this suggested searching for more complex configurations that must also be part of an unavoidable set with the hope that these more complicated configurations could somehow be shown to be reducible. For example, in 1903 Paul Wernicke proved that every cubic map containing no k-gon where k < 5 must either contain two adjacent pentagons or two adjacent regions, one of which is a pentagon and the other a hexagon (see Chapter 5). That is, the troublesome case of a cubic map containing a pentagon could be eliminated and replaced by two different cases. Finding new, large unavoidable sets of configurations was not a problem. Find￾ing reducible configurations was. In 1913 the distinguished mathematician George David Birkhoff (1884–1944) published a paper called The reducibility of maps in which he considered rings of regions for which there were regions interior to as well as exterior to the ring. Since the map was a minimum counterexample, the ring to￾gether with the interior regions and the ring together with the exterior regions could both be colored with four colors. If two 4-colorings could be chosen so that they match along the ring, then there is a 4-coloring of the entire map. Since this can always be done if the ring consists of three regions, rings of three regions can never appear in a minimum counterexample. Birkhoff proved that rings of four regions also cannot appear in a minimum counterexample. In addition, he was successful