DAM 9679 S0166-218X(16)30403-6 10.1016/j.dam.2016.09.011 The Author(s) Fig. 6.1 In the top panel is the parenteda -graphG x y * , the only member ofA * of order 12; in the bottom panel are the two components of its state transformation graph. Fig. 6.2 Schematic depiction of ana -graphG created by deleting an edge in an arbitrary internally 6-connected planar triangulation. Vertices within the sides of the interior squareu ' x ' v ' y ' and vertices and edges interior to that square have not been displayed. Fig. 6.3 A coloring of anR ( 6 , 7 ) conforming configuration that arises from the Errera triangulation of order 17 (see[11]). The colors ofx andy (the left and right boundary vertices, respectively, not shown) are both 1 and the colors ofu andv (the bottom and top boundary vertices, respectively, not shown) are both 2. Thea -graph coloring problem J.A. Tilley jimtilley@optonline.net 61 Meeting House Road, Bedford Corners, NY 10549, USA1 1 Retired, unaffiliated. 61 Meeting House Road Bedford Corners NY 10549 USA Abstract No proof of the 4-color conjecture reveals why it is true; the goal has not been to go beyond proving the conjecture. The standard approach involves constructing an unavoidable finite set of reducible configurations to demonstrate that a minimal counterexample cannot exist. We study the 4-color problem from a different perspective. Instead of planar triangulations, we consider near-triangulations of the plane with a face of size 4; we call any such graph ana -graph. We state ana -graph coloring problem equivalent to the 4-color problem and then derive a coloring condition that a minimala -graph counterexample must satisfy, expressing it in terms of equivalence classes under Kempe exchanges. Through a systematic search, we discover a family ofa -graphs that satisfy the coloring condition, the fundamental member of which has order 12 and includes the Birkhoff diamond as a subgraph. Higher-order members include a string of Birkhoff diamonds. However, no member has an applicable parent triangulation that is internally 6-connected, a requirement for a minimal counterexample. Our research suggests strongly that the coloring and connectivity conditions for a minimal counterexample are incompatible; infinitely manya -graphs meet one condition or the other, but we find none that meets both. Keywords 4-color problem Minimal counterexample Kempe exchange Equivalence class Birkhoff diamond 1 Graph terminology We use standard graph terminology. All graphs considered in this article are assumed to be planar unless otherwise stated.V ( G ) denotes thevertex setof the graphG . Two vertices areadjacentif they share an edge. Such an edge is said to beincidentto the two vertices it joins. Atriangulationis a graph in which all faces are delineated by three edges and anear-triangulationis a graph in which all faces but one are delineated by three edges. In this article, we refer to the edges delineating the sole non-triangular face in a near-triangulation as theboundaryof the graph and the vertices on the boundary asboundary vertices. Vertices not on the boundary are referred to asinterior vertices. Aninternal pathis one having no edge on the boundary. Aseparatingn -cycleinG has vertices ofG both inside and outside then -cycle. A connected graph isk -connectedif it has more thank vertices and remains connected whenever fewer thank vertices are deleted. In anr -regulargraph, all vertices have degreer . Aproper vertex-coloringofG is a coloring ofV ( G ) in which no two adjacent vertices have the same color. The only graph colorings we consider are proper vertex-colorings; we often refer to them merely ascolorings. We use the numbers 1, 2, 3, 4,..., to denote the different colors available for coloring a graph. We often use the term 4-coloringto mean any coloring using no more than 4 colors. The expressionc ( w ) translates asthe color of vertexw in the coloringc . AKempe chainis a maximal connected subgraph ofG whose vertices in a coloring ofG use only two colors. A Kempe chain that uses the colorsj andk is referred to as aj - k chain. A vertexw coloredj that is not adjacent to any vertex coloredk <> j is asingle-vertexorshortj - k Kempe chain. Exchanging colorsj andk for such a chain is the same as changing the color ofw tok . For purposes of this article, aKempe exchangeis a recoloring ofG in which the colorsj andk are exchanged in a designated, non-empty, proper subset of allj - k Kempe chains. For example, ifG has three pairwise disjoint 1-2 Kempe chains, then exchanging colors on any one or any two counts as a single Kempe exchange. 2 Introduction This article is primarily about discovering why the 4-color conjecture is true. No existing proof[1,2,8,9]accomplishes that - it was never the goal. Succeeding at the endeavor may open up a new avenue by which the 4-color conjecture can ultimately be proved without relying on a computer. Even if that turns out not to be the case, we contend that it is worthwhile trying to understand what it is that renders the 4-color problem solvable. In its tightest formulation, the statement of the 4-color problem is to show that any planar triangulation has a 4-coloring. Instead of planar triangulations, we study near-triangulations of the plane in which the sole non-triangular face has size 4. We call any such near-triangulation ana -graphbecause it is an "almost-triangulated-graph". Instead of the 4-color problem, we study thea -graph coloring problem. Thea -graph coloring problem Letx y be any edge in an arbitrary planar triangulationT . Show that thea -graphG = T - x y has a 4-coloringc in whichc ( x ) <> c ( y ) . The 4-color problem and thea -graph coloring problem are trivially equivalent. Start with an uncoloredT and delete the edgex y , give the resultingG a coloringc that solves thea -graph coloring problem, then replace the edgex y to obtain a 4-coloring ofT . Conversely, start with an uncoloredG , insert the edgex y , give the resultingT a coloringc that solves the 4-color problem, then delete the edgex y to obtain the required 4-coloring ofG . What can possibly be achieved by this near sleight-of-hand? What is the motivation for studying thea -graph coloring problem? The answers lie in examining all distinct colorings of bothT andG . Obviously, all colorings ofT are colorings ofG . But there are coloringsc ofG in whichc ( x ) = c ( y ) that are not colorings ofT . Generally, many of these will be Kempe-equivalent to colorings ofT . This observation underpins our approach.The key concept is to obtain a proper coloring of some target graph, say the triangulationT , by using colorings of a related graph, say thea -graphG , that are not proper colorings ofT but are Kempe-equivalent to proper colorings ofT .Suppose that any triangulation of lower order thanT has a 4-coloring, either becauseT is a minimal counterexample or purely as an inductive assumption. By contracting the edgex y inT rather than deleting it, we obtain a triangulation that can be given a 4-coloringc . Upon reversing the contraction without restoring thex y edge, we arrive atG with 4-coloringc in whichc ( x ) = c ( y ) and can then proceed to analyze thea -graph coloring problem, attempting to navigate by means of Kempe exchanges fromc to a 4-coloringc ' in whichc ' ( x ) <> c ' ( y ) . It is useful to enhance our notation regarding the designation and description of ana -graphG . We establish the convention of always drawingG with the 4-face as an exterior face and orienting that 4-face as shown inFig. 6.1, labeling the boundary cycleu x v y , thus establishing( x , y ) and( u , v ) as the two pairs ofopposite (non-adjacent) boundary vertices. Then we can refer to the twoparent triangulationsof anya -graphG asG + x y andG + u v . We always denote the left-hand vertex on the 4-face byx , the right-hand vertex byy , the bottom vertex byu , and the top vertex byv . With respect to graph structure, the sameG results whether the edgex y is deleted in the parentG + x y or the edgeu v in the parentG + u v . For some purposes, it will suffice to discussG without reference to a specific parent triangulation, but for many purposes it will not, and in those situations theapplicable parentneeds to be designated. When that is the case,G is best thought of as two different graphs, one with parentG + x y and one with parentG + u v . In the first case, we refer to theparenteda -graphasG x y , and in the second case, we refer to theparenteda -graphasG u v . A helpful reminder as to which parent is applicable is to think ofG x y as having aghost edgex y and ofG u v as having aghost edgeu v . Clearly the parenteda -graphsG x y andG u v can differ as to the connectivity of their respective applicable parents and we shall see that they can also differ as to how their equivalence classes under Kempe exchanges are categorized, both matters crucial to determining whether they can be minimala -graph counterexamples. So, for example,G x y might be a minimala -graph counterexample whileG u v is not. Thus the need to distinguish between them. When thea -graph coloring problem forG applies to the( x , y ) pair, we refer toG asG x y , and when thea -graph coloring problem forG applies to the( u , v ) pair, we refer toG asG u v . When we talk about the structure of ana -graph without reference to a particular pair of opposite boundary vertices, we simply refer to thea -graph asG . For instance, we might simply say thatG has minimum degree 4. 3 Overview In line with other work, ours is based on the notion of a minimal counterexample. To be a minimal counterexample to the 4-color conjecture, a planar triangulation must beinternally 6-connected. An internally 6-connected triangulation has minimum degree 5 and no separating 3-cycles or 4-cycles. Further, if any separating 5-cycle is removed, at least one of the components created has only a single vertex. A lucid description of this property can be found in both[8,9]. There are aninfinite number of internally 6-connected planar triangulations, each of which is potentially a minimal counterexample. Without a method to sort through them, to characterize and classify them, each would have to be examined individually, an impossible task. That is why mathematicians directed their efforts in the early 1970s towards constructing afiniteset of configurations that are bothunavoidableandreducible. (Refer to[14].)Our approach is different.Rather than offer yet another unavoidable set of reducible configurations, we ask: Is there some property we can use to winnow the infinite set down to a set with a distinguishing characteristic that renders it amenable to straightforward analysis? There does appear to be, one that is readily expressed fora -graphs. Thiscoloring propertyis the subject of Section5. To state the coloring property efficiently, we introduce the concept of astate transformation graphto depict the partitioning of the set of all distinct colorings of a given parenteda -graph into equivalence classes under Kempe exchanges. We label any class one of three types. We express the coloring property as the absence of one of those types. The set of parenteda -graphs exhibiting the coloring property we refer to as the familyA * . In Section6, we provide a heuristic, but compelling, argument as to why afundamentalmember ofA * , one without repetitions of a nontrivial configuration, is expected to have low order. Thus, we can reasonably limit the search for fundamental members ofA * toa -graphs of order at most 20. In retrospect, this restriction appears to have been justified: the search turned up only a single fundamental member and it has order 12. We refer to that member asG * , and, using our conventions and enhanced notation, more precisely as the parenteda -graphG x y * ofFig. 6.1. So,G x y * ? A * , but its applicable parent triangulation is not internally 6-connected. The icosahedron is the applicable parent ofG u v * . It is internally 6-connected, butG u v * ? A * . Aminimala -graph counterexamplemust have an internally 6-connected parent, and,with that parent, belong toA * . In a sense,G * comes close, but it isG x y * that belongs toA * andG u v * with the internally 6-connected parent. Our systematic search found no parenteda -graph that satisfies the coloring condition and whose applicable parent is internally 6-connected. That is our key result. It points to why a minimal counterexample does not exist - the coloring and connectivity conditions are incompatible. To be clear, we have not proved that statement, but our research strongly suggests it. In a future article, we will show that the methodology described in this article can be used to determine when Kempe chain entanglements are resolvable and when they are not, and also how to resolve them when they are not. Most significantly, no sequence of Kempe exchanges can resolve entangled Kempe chains to find a coloring that solves thea -graph coloring problem fora -graphs belonging to the familyA * . In the future article, we implement an algorithm that maps out components of a state transformation graph and use it to demonstrate that an explicit solution to thea -graph coloring problem can be always be found by Kempe exchanges fora -graphs derived from the well-known Errera, Heawood, and Kittell triangulations[11-13]. 4 Connectivity property of a minimala -graph counterexample In a 1913 article[3], Birkhoff proved that a minimal counterexample to the 4-color conjecture must be internally 6-connected. (He did not use this particular term, but it has become standard.) We show that this condition essentially applies to thea -graph coloring problem. Suppose there is a parenteda -graphG x y such that the color ofx is the same as the color ofy in every 4-coloring ofG x y . ThenG x y is said to be ana -graph counterexample. Aminimala -graph counterexampleis ana -graph counterexample for which there is noa -graph counterexample of lower order. It is natural to think that whatever connectivity property applies to a minimal counterexample to the 4-color conjecture automatically translates to an equivalent property for a minimala -graph counterexample. This turns out to be right. Theorem 4.1 Deleting any edge in a minimal counterexample to the4-color conjecture results in a minimal a -graph counterexample. Proof Suppose that a planar triangulationT is a minimal counterexample to the 4-color conjecture. Letx y be an arbitrary edge inT . Deletex y to form a parenteda -graphG x y . SupposeG x y is not ana -graph counterexample. Then there exists a 4-coloringc such thatc ( x ) <> c ( y ) . When the edgex y is inserted,c becomes a 4-coloring ofT , contradicting the supposition. Suppose thatG x y is not aminimala -graph counterexample. Then there exists a parenteda -graphG x ' y ' ' of lower order thanG x y that is ana -graph counterexample with a pair of opposite boundary vertices( x ' , y ' ) that in any 4-coloring ofG x ' y ' ' must be colored the same. However, the triangulationT ' formed by inserting an edgex ' y ' must be 4-colorable sinceT ' has lower order thanT . By deleting the edgex ' y ' , we obtain a 4-coloring ofG x ' y ' ' in whichx ' andy ' are not colored the same, a contradiction.? Theorem 4.2 SupposeG x y is a minimala -graph counterexample. Then the triangulationG x y + x y is a minimal counterexample to the4-color conjecture. Proof Becausec ( x ) = c ( y ) in all 4-coloringsc ofG x y , the parent triangulationT formed fromG x y by inserting an edgex y is a counterexample to the 4-color conjecture, and it is a minimal counterexample because if it were not thenG x y would not be a minimala -graph counterexample.? We say that ana -graph isinternally 6a-connectedif at least one of its two parent triangulations is internally 6-connected. Corollary 4.1 A minimala -graph counterexample is internally6a-connected. 5 Coloring property of a minimala -graph counterexample In a 1975 doctoral thesis[10], a year before Appel and Haken announced their proof of the 4-color conjecture, Stromquist showed that a minimal counterexample must have order 52 or higher. That result translates directly to thea -graph coloring problem. For thea -graph perspective to bring something new to the 4-color problem, we must discover a property of a minimal counterexample that, when combined with internal 6-connectedness, is so highly restrictive that it eliminates the possibility that a minimal counterexample exists. A promising candidate is a particular coloring property applying toa -graphs, one that is most clearly expressed in terms of equivalence classes under Kempe exchanges. Remark 5.1 The use of equivalence classes under Kempe exchanges to study various graph-coloring problems is not new. Others[4-7]have used them in connection with thek -coloring ofk -regular graphs, the 4-coloring of Eulerian triangulations of the plane, and Hadwiger's conjecture. We often refer to a particular 4-coloring of a parenteda -graphG as acoloring stateofG or simply astateofG . Two 4-colorings ofG represent the same state if they lead to the same partition ofV ( G ) into color classes. LetC G denote the set of states ofG . Kempe exchanges induce an equivalence relation among those states and can thus be used to partitionC G into equivalence classes, each such class a component of thestate transformation graphassociated withG . The state transformation graph has the states ofG as vertices, two states being adjacent if they are connected by a single Kempe exchange. Consider a parenteda -graphG x y . Any state in whichc ( x ) <> c ( y ) we call asolution statefor obvious reasons and therefore any state in whichc ( x ) = c ( y ) we call anon-solution state. Any equivalence class all of whose states are non-solution states we label ann class, and one for which all states are solution states we label ans class. Any equivalence class for which some states are non-solution states and some are solution states we label ann - s class. In terms of solving thea -graph coloring problem, anyG x y which has ann - s class or ans class is one with which we do not have to concern ourselves. AnyG x y which has onlyn classes (or a singlen class) is ana -graph counterexample. Remark 5.2 The composition of a particular equivalence class - specifically, what coloring states constitute the class - does not depend on whether it isG x y orG u v that is being considered, but the labelsn , s , orn - s that are attached to the various equivalence classes do. Since the motivation for studying thea -graph coloring problem in lieu of the 4-color problem is to bring non-solution states into the picture to serve as starting points to allow Kempe exchanges to find solution states, it makes sense to distinguish parenteda -graphs by whether or not they have at least onen - s class. All parenteda -graphs which lack ann - s class we deem particularly worthy of consideration and we use that characteristic to define the familyA * . Definition 5.1 A parenteda -graphG x y belongs to the familyA * if and only if the Kempe partition ofC G x y has non - s class. Theorem 5.1 A minimal a -graph counterexample belongs to A * . Proof LetG x y be a minimala -graph counterexample. SupposeG x y ? A * . Then there is at least one non-solution state ofG x y equivalent to a solution state under Kempe exchanges, contradicting the supposition.? Lemma 5.1 Letc be a non-solution state ofG x y ? A * . Then there exist2-color paths between x and y for all three color-pairings that include the common color of x and y . Proof Without loss of generality, we havec ( x ) = c ( y ) = 1 . Suppose there is no 1-k path betweenx andy for somek <> 1 . Then there is a 1-k Kempe chain (perhaps a short chain) that includesy but notx . Exchanging colors on that chain yields a solution state and indicates the presence of ann - s class, contradicting the statement thatG x y ? A * . Thus, there is a 1-k path betweenx andy fork = 2 , 3 , and4.? Lemma 5.2 Letc be a solution state ofG x y ? A * . Then there exists a2-color path between x and y . Proof Without loss of generality, we havec ( x ) = 1 andc ( y ) = 2 . Suppose there is not a 1-2 path betweenx andy . Then there is a 1-2 Kempe chain (perhaps a short chain) that includesy but notx . Exchanging colors on that chain yields a non-solution state forG x y and indicates the presence of ann - s class, contradicting the assumption thatG x y ? A * . Thus, there is a 1-2 path betweenx andy .? Lemma 5.3 G x y ? A * if and only if in every non-solution state there is no2-color path between u and v using colors different from the common color of x and y . Proof Letc be an arbitrary non-solution state. Without loss of generality, we can assign colors so thatc ( x ) = c ( y ) = 1 , c ( u ) = 2 , andc ( v ) = 2 or 3. Supposec ( v ) = 2 . Then there are two 1-2 boundary paths betweenx andy . Assume there is no 2-3 or 2-4 internal path betweenu andv . ByTheorem A.1(Appendix A), there must be both 1-4 and 1-3 internal paths betweenx andy . Suppose instead thatc ( v ) = 3 . Then there are 1-2 and 1-3 boundary paths betweenx andy . Assume there is no 2-3 internal path betweenu andv . ByTheorem A.1, there must be a 1-4 internal path betweenx andy . In either case, no 1-2 or 1-3 or 1-4 Kempe exchange can result in a solution state. Nor can any Kempe exchange not involving the color 1. Because this is true for every non-solution state ofG x y , it follows that no sequence of Kempe exchanges starting withc can lead to a solution state. Thus, there is non - s class in the partition ofC G x y , and byDefinition 5.1,G x y ? A * . Conversely, assume thatG x y ? A * . Again, letc be an arbitrary non-solution state withc ( x ) = c ( y ) = 1 , c ( u ) = 2 , andc ( v ) = 2 or 3. Supposec ( v ) = 2 . Then, byLemma 5.1, there must be 1-3 and 1-4 internal paths betweenx andy , and byTheorem A.1, there can be no 2-4 or 2-3 internal path betweenu andv . Suppose instead thatc ( v ) = 3 . Then byLemma 5.1, there must be a 1-4 internal path betweenx andy , and byTheorem A.1, there can be no 2-3 internal path betweenu andv .? 6 The search for members ofA * Though we are interested in finding any member ofA * , we are particularly interested in finding one that is a potential minimala -graph counterexample. The applicable parent triangulation of a minimala -graph counterexample must be internally 6-connected; thus, among other attributes, that parent must have minimum degree 5. Because we need the terminology for later use, we prove the well-known result that such a triangulation must have order at least 12. Lemma 6.1 A minimum degree5planar triangulation has order at least12. Proof Letv , e , andf denote the number of vertices, edges, and faces, respectively, in a planar triangulationT . Letd v denote the sum over all vertices inT of the degrees of those vertices. Thend v = 2 e = 3 f . Using Euler's formula,v - e + f = 2 , we derived v = 6 v - 12 . BecauseT has minimum degree 5,d v >= 5 v . It follows thatv >= 12 .? By tedious enumeration of all possible cases, it is straightforward to show, usingLemma 5.3, that anyG x y ? A * must have order at least 12 and that the only member ofA * of order 12 is the one depicted in the top panel ofFig. 6.1- it is the graph we identified in Section2asG x y * . The bottom panel shows the two equivalence classes in the state transformation graph forG * whetherG * is considered to beG x y * orG u v * . Each coloring state has been labeled using a pair of arithmetic signs, the first applying to the coloring of the( x , y ) pair of opposite boundary vertices and the second applying to the coloring of the( u , v ) pair. An = sign means that the vertices in the pair are colored the same; a<> sign means that the vertices in the pair are not colored the same. This labeling indicates that for the parenteda -graphG x y * there is ann class with 6 states and ans class with 12 states. Thus,G x y * ? A * . However, even without finding solution states, we knew thatG x y * could not be a minimala -graph counterexample because its applicable parent triangulation,G x y * + x y , is not internally 6-connected: whenx andy are joined,u andv have degree 4. The other parent triangulation,G u v * + u v , is internally 6-connected - it is the 5-regular icosahedron. For the parenteda -graphG u v , the arithmetic signs in the second position apply; we see that there are non-solution states and solution states in each component. Both equivalence classes aren - s . Thus,G u v * ? A * . ClearlyG u v * is not a minimala -graph counterexample either. Thea -graphG * is extraordinary:G x y * ? A * , but its applicable parent is not internally 6-connected;G u v * ? A * , but its applicable parent is internally 6-connected. Aminimala -graph counterexamplemust have an internally 6-connected parent, and, with that parent, belong toA * - that is the type ofa -graph we are looking for. However, we shall see thatG * is likely as close as we can get. Remark 6.1 Fig. 6.1discloses an interesting fact about the various colorings of the icosahedron. In the bottom panel, if we eliminate all vertices that are labeled with an = sign in the second position, we are left with ten vertices of degree 0 - this is the state transformation graph for the icosahedron. There are ten distinct colorings, none of which is obtainable from any other by means of Kempe exchanges. However, when theu v edge is deleted from the icosahedron, the state transformation graph forG u v * shows that non-solution states in the component of order 6 connect four of the colorings of the icosahedron. Similarly, non-solution states in the component of order 12 connect six of the colorings of the icosahedron. Starting from any non-solution state ofG u v * , we can navigate to a solution state and thus to a proper 4-coloring of the icosahedron. In what sense does the "smallness" of ana -graph give it a chance to be a member ofA * ? ForG x y * , there are only teninternalpaths betweenu andv that use no more than a single edge of any triangle and therefore can be 2-colored and maintain a proper coloring of the overalla -graph. ForG x y * as drawn inFig. 6.1, those ten paths come in mirror-image pairs under reflections in theu - v axis. Thus, there are effectively only five distinct paths that can possibly be 2-colored. If we take an uncoloredG x y * , assignx andy color 1, then select any of those five paths and give it a 2-coloring not involving the color 1, we find that the vertices already colored force the coloring of most, if not all, of the remaining uncolored vertices. Any attempt to color the remaining vertices requires at least one uncolored vertex to be assigned a fifth color. Thus, there is a relatively small number ofcoloring degrees of freedomforG x y * and that leads to forced color assignments at many vertices and inevitably to the need for a fifth color. The same factors will apply to any member ofA * . Our search for fundamental members ofA * will therefore focus on small graphs, which, for purposes of this study, we take to be alla -graphs of order not exceeding 20. Systematic search Because we are looking particularly for minimala -graph counterexamples, we will confine our exploration toa -graphsG that are internally 6a-connected. To organize the search efficiently, it is useful to have a taxonomy for sucha -graphs. The general structure is depicted inFig. 6.2. This depiction derives from drawing the paths including vertices adjacent to each of the boundary verticesu , x , v , andy , and noting that the paths for two adjacent boundary vertices must have a vertex in common becauseG is a near-triangulation. The four such shared vertices have been designatedu ' , x ' , v ' , andy ' inFig. 6.2. Not shown are any vertices inserted into thesidesof thecentral squareu ' x ' v ' y ' or any vertices and edges enclosed by that square. We refer to the boundary 4-cycleu x v y as theouter ringofG and the cycle that includesu ' , x ' , v ' , andy ' and all vertices inserted into any or all of the central square's four sides as theinner ringofG . Even thoughinner ringis a properly precise term, we will often find it convenient to refer more loosely tou ' , x ' , v ' , andy ' as thecorner verticesof the square and to the paths betweenu ' andx ' , betweenx ' andv ' , betweenv ' andy ' , and betweeny ' andu ' , in each case adjacent to a boundary vertex, as the foursidesof the square. Any vertices in the sides that are not corner vertices are said to beside vertices. We say thatG belongs to the familyG ( m , n ) if its inner ring is of ordern and enclosesm interior vertices. The familyR ( m , n ) derives from taking all graphs inG ( m , n ) and eliminating their outer rings of order 4 and all edges incident to those outer rings. Up to an isomorphism, a particulara -graphG is uniquely specified by selecting from the applicable familyR ( m , n ) a particular arrangement of corner, side, and interior vertices, and the edges that join them. Any near-triangulationR ? R ( m , n ) is referred to as aconfiguration. Definition 6.1 A configurationR ? R ( m , n ) is said to beconformingif the following conditions hold:i. the corner verticesu ' , x ' , v ' , andy ' ofR have minimum degree 3, ii. there are at least two side vertices inR , one each in a pair of opposite sides, iii. then - 4 side vertices ofR have minimum degree 4, iv. them vertices interior to the boundary ring ofR have minimum degree 5, v. there is no separating triangle or quadrilateral inR , vi. the only separating pentagons inR , if removed, would leaveR disconnected into two components, at least one of which has but a single vertex, vii. every vertex in the boundary ring ofR is adjacent to two and only two other vertices in the boundary ring. Conditions i through vi assure that thea -graph arising from a conforming configuration is internally 6a-connected. Condition vii is implied by the other conditions buthas been included to aid in constructing conforming configurations. If there were an edge between vertices in the boundary ring ofR that would otherwise be separated by a distance of at least 2, there would be a violation of one or more of conditions i through vi. The goal of the systematic search is to find all conformingR up to a given order and then determine which satisfy the coloring condition ofLemma 5.3. Lemma 6.2 The m + n interior vertices of G ? G ( m , n ) have average degree equal to 5 + ( m - 2 ) / ( m + n ) . Proof We use the result developed in the proof ofLemma 6.1thatd v = 6 v - 12 for a planar triangulationT of orderv . Leta -graphG be formed by deleting an edge inT . Usingd v to represent the sum over all vertices inG instead ofT eliminates a count of 2 fromd v and transforms the equation tod v = 6 v - 14 , now applying toG instead ofT . We distinguish between boundary and interior vertices ofG by introducingd b andd i to represent the sum of the degrees over those two respective sets of vertices. Thend v = d b + d i . Also,v = m + n + 4 . Substituting these into the previous result, we obtaind b + d i = 6 ( m + n ) + 10 . Becaused b counts two boundary edges for each boundary vertex and counts each of the four corner vertices on the inner ring twice, we haved b = n + 12 . Thus,d i = 5 ( m + n ) + ( m - 2 ) . Dividing this bym + n , the number of interior vertices, yields the desired result.? Lemma 6.3 IfG ? G ( 0 , n ) orG ( 1 , n ) , thenG is not internally6a-connected. Proof Whenm = 0 or 1,Lemma 6.2shows that the average degree of the interior vertices is less than 5, implying that at least one interior vertex has degree less than 5.? Lemma 6.4 IfG ? G ( 2 , n ) , thenG is not internally6a-connected unless G is isomorphic to G * . Proof LetG ? G ( 2 , n ) .Lemma 6.2indicates that the interior vertices ofG have average degree 5. IfG is internally 6a-connected, its interior vertices must have minimum degree 5. Thus, all interior vertices ofG have degree 5. We buildG with this property by constructing its conforming configurationR . By condition ii ofDefinition 6.1, we haven >= 6 . Without loss of generality, letp be the vertex in the side fromx ' tov ' that is adjacent tov ' andq be the vertex in the side fromu ' toy ' that is adjacent toy ' . Letr ands be the two vertices interior to the boundary ring ofR . By conditions iii and vii,p andq must each be joined to bothr ands , andr ands must be joined to each other. To satisfy condition i without violating condition vii,v ' andy ' must each be joined to one ofr ands andx ' andu ' to the other. The addition of any further side vertices will violate condition iii. With this construction, we note that condition iv is satisfied for bothr ands , and that conditions v and vi are satisfied forR . Thus, we arrive at the conforming configurationR belonging toR ( 2 , 6 ) that is isomorphic to the one depicted inFig. 6.1as a subgraph ofG * .? Constructing the conforming configurations Because we are looking forG that are internally 6a-connected,Definition 6.1andLemmas 6.3 and 6.4mean that we need consider only conforming configurationsR ( m , n ) for whichm >= 3 andn >= 6 , and because we are limiting our search toG of order at most 20, we must construct all such configurations for whichm + n =< 16 . A key operation in the construction process is adiamond switchin which the edge joining one pair of opposite boundary vertices in aK 1 , 1 , 2 diamond is switched to joining the other pair of opposite boundary vertices. The complete process involves the following steps.1. Setm = 3 andn = 6 . Fix the four corner verticesx ' , v ' , y ' , andu ' for the ringR of a conforming configuration. 2. Select a 4-partition{ n 1 , n 2 , n 3 , n 4 } ofn - 4 that has not already been processed for the givenm . If all partitions have been processed, skip to step 5. Placen 1 , n 2 , n 3 , andn 4 side vertices in the four sidesx ' tov ' , v ' toy ' , y ' tou ' , andu ' tox ' , respectively, accepting the ring only if there is a pair of opposite sides that have at least one vertex each. Reject the ring if it is isomorphic to one already processed and keep repeating this step 2, as necessary, until a distinctly new ring has been created. 3. Create one or morerepresentativeconforming configurations by inserting, within the ring established in step 2,m vertices arranged as a path or tree or cactus or polygon or kite or any of those enclosed by a polygon of order at least 6 or as a single vertex enclosed by polygon of order at least 5. If this is impossible to accomplish, return to step 2. 4. For the givenm , n , and partition ofn - 4 , create all conforming configurations by taking the representative configurations created in step 3 and performing all possible sequences of diamond switches. Whenever a sequence of switches ends with a configuration that is either nonconforming or isomorphic to a conforming configuration that has been previously created, discard it and continue until no new non-isomorphic conforming configuration can be created. Return to step 2. 5. Increasem by 1. Ifm + n =< 16 , return to step 2. 6. Increasen by 1. Setm = 3 . Ifm + n =< 16 , return to step 2. Appendix Bdisplays the representative configurations used in the search. Coloring the conforming configurations Every conforming configuration needs to be tested to determine if the correspondinga -graph with boundary verticesu , x , v , andy in place belongs toA * .Lemma 5.3provides the criterion for membership. Depending on the partition of side vertices in the conforming configuration, one parent triangulation can be internally 6-connected while the other is not. Regardless, the correspondinga -graph is internally 6a-connected and we test bothG x y (for the presence or absence of an internal 2-color path betweenu andv ) andG u v (for the presence or absence of an internal 2-color path betweenx andy ). Often we can find a single coloring in which bothx andy are colored 1 and bothu andv are colored 2 and there are both a 1-3 path betweenx andy and a 2-3 path betweenu andv or both a 1-4 path betweenx andy and a 2-4 path betweenu andv . In such a situation, the single coloring serves to prove thatG x y ? A * andG u v ? A * . That is the case, for example, for the particularR ( 6 , 7 ) conforming configuration shown inFig. 6.3. We found that in about half the cases tested, we had to generate two distinct colorings ofG , one applying to each parent. Results The systematic search turned up no new members ofA * . The coloring condition ofLemma 5.3is not satisfied by any conforming configuration other thanR ( 2 , 6 ) . There are, in fact, other members ofA * - for example, non-fundamental members of orders 19 and 20. Indeed, there are an infinite number of members. But not one was detected in our search because we imposed condition vii ofDefinition 6.1. Among other things, it forbids an edge between vertices in a pair of opposite sides of the central square. If that limitation is removed, we find that the phenomenon occurring forG x y * can be replicated as many times as we like by creating various parenteda -graphs, each including a different vertical string of Birkhoff diamonds with common endpointsx andy . The non-fundamental member of order 19 has two Birkhoff diamonds in such a string, as does the non-fundamental member of order 20. (The difference between those two non-fundamental members lies in how their two Birkhoff diamond subgraphs are connected.) Because none of the applicable parent triangulations withx andy joined is internally 6-connected, none of these particular non-fundamental members ofA * is a minimala -graph counterexample. Remark 6.2 The Birkhoff diamond is a configuration famous in the history of the 4-color problem. See[14]. It is the subgraph ofG * inFig. 6.1induced by all vertices other thanu andv . There is a heuristic argument (but not a proof) that underscores how unlikely it is that a minimala -graph counterexample exists. Let the planar triangulationT be a minimal counterexample to the 4-color conjecture. From the proof ofLemma 6.1, we know thate = 3 v - 6 , wheree andv are the number of edges and vertices, respectively, inT . From[10]we know thatv >= 52 . So, fromTheorems 4.1 and 5.1, we see thatT must be parent to at least 150 minimala -graph counterexamples and all must belong toA * . Because our search among internally 6a-connecteda -graphs of order at most 20 turned up only the graphG x y * ofFig. 6.1, it would indeed be stunning to suddenly happen upon a cache of at least 150. Of course, not all such minimala -graph counterexamples would necessarily be structurally different from one another. They could, and would likely, belong to a number of isomorphism classes less than 150. Still, regardless of how symmetricalT may be (when depicted in a manner to highlight its symmetries), it cannot be regular (because there is only oner -regular planar triangulation, the icosahedron, forr = 5 , and none forr > 5 ) and thus has to give rise to several, perhaps many, structurally distinct minimala -graph counterexamples of high order, a particularly implausible result given our previous heuristic argument that the order of any fundamental member ofA * is likely to be low. This line of reasoning leads to the conclusion that if there were to exist but a single structurally distinct minimala -graph counterexample, the icosahedron would have to be its applicable parent. 7 Conclusion Proving the 4-color conjecture entails showing that a minimal counterexample does not exist. The standard approach is to generate an unavoidable finite set of reducible configurations. Unlike the standard approach, we state acoloring conditionthat a minimal counterexample must satisfy. Our approach, which admittedly does not qualify as an alternative proof, also differs in other ways:1. Instead of considering a planar triangulation, we study thea -graph created by deleting an edge in that parenttriangulation. 2. Instead of considering the 4-color problem directly, we analyze an equivalent coloring problem, thea -graph coloring problem. 3. Instead of creating unavoidable reducible configurations, we search for members ofA * , the family ofa -graphs that satisfy the coloring condition. The only fundamental member ofA * that our systematic search discovered is the parenteda -graphG x y * that contains a single copy of the Birkhoff diamond as a subgraph. Non-fundamental members contain multiple copies of the Birkhoff diamond with common endpoints. None of the parenteda -graphs we have discovered that belong toA * satisfies the connectivity condition to be a minimala -graph counterexample: namely, that the applicable parent is internally 6-connected. Our research strongly suggests that there is no parenteda -graph that satisfies both the coloring condition and the connectivity condition. The two conditions appear to be incompatible. That is the likely reason that no minimal counterexample exists. A byproduct of our approach is the reaffirmation that Kempe chains play a critical role in solving the 4-color problem, despite the entanglement conundrum that Kempe's failed proof encountered (see[14]). Acknowledgments I would like to thank Fred Holroyd for his insights and comments regarding virtually all aspects of this article. I would also like to thank a referee for offering a succinct proof ofTheorem A.1. Appendix A Theorem A.1 LetG be ana -graph with boundary cycleu x v y for the exterior4-face and letG have a4-coloringc . Suppose, without loss of generality, thatc ( x ) = 1 , c ( y ) = 1 or2,c ( u ) = 3 , andc ( v ) = 3 or4. Then there is either a1-2path betweenx andy or a3-4path between u and v . Proof Suppose thatG with 4-coloringc is a minimal counterexample to the theorem. ClearlyG cannot have either an interiorx y edge or an interioru v edge. LetX be the set of vertices ofG adjacent tox ; they form an internal path betweenu andv that includes at least one interior vertex ofG . At least one of those interior vertices ofG belonging toX is colored 2, for otherwise the path betweenu andv would be colored 3-4, contradicting the supposition. Contract the various edges joiningx to each vertex ofX colored 2, and change the color ofx to 2. The result is a 4-coloreda -graphF . The edge contractions do not create any 3-4 path betweenu andv . By the minimality assumption,F must therefore have a 1-2 path betweenx andy . Reverse the contractions and restore the color ofx to 1 to reveal a 1-2 path betweenx andy inG , contradicting the supposition and establishing the truth of the theorem.? Appendix B This appendix lists the 106 representative conforming configurations used to generate all internally 6a-connecteda -graphs of order 20 or lower. The first,R ( 2 , 6 ) , leads toG x y * , the only fundamental member ofA * that we have discovered. The configurations are listed by increasing order and, within a given order, by increasing number of interior vertices. For a givenm andn , representative conforming configurationsR ( m , n ) for all non-isomorphic partitions of side vertices among the four sides of the ring are listed. Conforming configurations for some partitions do not exist - for example, forR ( 3 , 8 ) , R ( 4 , 10 ) , andR ( 5 , 11 ) , only one partition of side vertices is shown because there are no conforming configurations for any other partition. In a few instances, two or three representatives are listed for a given partition - for example,R ( 4 , 8 ) . In that particular case, there is a sequence of seven diamond switches that transforms one representative configuration into the other with no intermediate stage that is conforming. To reduce the number of complicated sequences of switches required to generate all possiblea -graphs, different representative arrangements of interior vertices for the same partition of side vertices have been included. Another example isR ( 6 , 7 ) - each of the two representatives for one of the partitions can be diamond-switched intoFig. 6.3: two switches for one of the representatives and only one switch for the other. For some representatives there is a large number of different sequences of diamond switches that lead to non-isomorphic conforming configurations with the same partition of side vertices. References [1] K. Appel W. Haken Every planar map is four colorable, part i: Discharging Illinois J. Math. 21 3 1977 429 490 [2] K. Appel W. Haken J. Koch Every planar map is four colorable, part i: Reducibility Illinois J. Math. 21 3 1977 491 567 [3] G. Birkhoff The reducibility of maps Amer. J. Math 70 1913 114 128 [4] S. Fisk Geometric coloring theory Adv. Math. 24 3 1977 298 340 [5] M. Las Verngas H. Meyniel Kempe classes and the hadwiger conjecture J. Combin. Theory Ser. B 31 1 1981 95 104 [6] H. Meyniel Les 5-colorations d'un graphe planaire forment une class de commutation unique J. Combin. Theory Ser. B 24 3 1978 251 257 [7] B. Mohar Kempe equivalence of colorings Graph Theory in Paris 2007 Birkhauser Basel [8] N. Robertson P. Sanders P. Seymour R. Thomas The four-color theorem J. Combin. Theory Ser. B 70 1 1997 2 44 [9] J. Steinberger, An unavoidable set of d-reducible configurations.arXiv:0905.0043v3[math.CO], 2009. [10] W. Stromquist Some Aspects of the Four Color Problem (Ph.D. thesis) 1975 Harvard University [11] E. Weisstein, Errera graph.MathWorld - A Wolfram Web Resource,http://mathworld.wolfram.com/ErreraGraph.html. [12] E. Weisstein, Heawood four-color graph.MathWorld - A Wolfram Web Resource,http://mathworld.wolfram.com/HeawoodFour-ColorGraph.html. [13] E. Weisstein, Kittell graph.MathWorld - A Wolfram Web Resource,http://mathworld.wolfram.com/KittellGraph.html. [14] R. Wilson Four Colors Suffice 2002 Princeton University Press