THE FOUR COLOR THEOREM AND THREE PROOFS

 

 

I. Cahit[*]

 

 

 

Abstract

 

In August 2004 the author has introduced spiral chains for  the maximal planar graphs in the sequel of a non-computer proof of the famous four color theorem.  A year later he has  also given an independent proof of the equivalent problem of three-edge coloring of bridgeless cubic planar graphs which is known as Tait’s reduction, also  by the use of  spiral-chains. Recently I have considered the well-known Kempe’s fallacious proof from the point of counter-examples.  In case of an counter-example or bad-example to Kempe’s argument,  we have abled to extend the given incomplete four coloring of the bad-example to an proper four coloring of the whole maximal planar graph. Here the proof proposed uses double spiral chains which is started from the undecided node of the graph and traverses clock or counter-clockwise direction the other nodes in the shape  of  two parallel spirals (double-spirals).     

 

 

INTRODUCTION

 

The famous four color problem is to color the regions of a given map using least number of colors so that adjacent regions have different colors. The story of the problem as well as its known proofs is very long and tedious [1],[6],[2]. There are several historical false elegant proofs [7],[9],[10-12]. Many books and articles have been published on the problem so I leave it to the reader to choose his  own selection. Robin Thomas has listed many equivalent formulations of the four color theorem in [18]. My selection about the four color problem and theorem  would be shortest and simplest, if there are any.

In recent talk Neil Robertson has said: “The four-color theorem for planar graphs continues to stimulate the development of chromatic graph theory. Most mathematicians would like to see the reliance on the computer in the proof reduced. A direct approach would involve developments in the theory of Kempe chains [4],[5]. Indirectly, the dual forms of the theorem involving vertex colorations or facial colorations generalize in different ways. These extensions should lead to new techniques, as they are longstanding open problems, and some of these may apply to the theorem itself”.  Good news about the strong supporters of the computer-aided proofs is the announcement of  Gonthier’s verification of the correctness of the four-color theorem in Coq [2]. Our aim from this paper is several fold first is  to convinced the reader that the use of spiral chains would add more visual abstraction to the proof of the theorem, secondly is the possibility of the use of spirals in the other similar graph coloring problem and lastly is to show that the spiral-chain technique is powerful enough to devise a non-computer proofs for the four color map theorem in three different ways [8],[15],[16].  

 

 

 

In this paper we have summarized the three proof techniques to four color theorem. Actually except the first one the last two methods are not really new but the tool “spiral-chain” in graphs or maps is a new and original idea.

The first idea is to give an algorithmic direct proof with the termination condition and valid for any given maximal planar graph, that is we have shown that spiral-chain coloring algorithm always color the nodes of the maximal planar graph  with four colors or less.

The second idea is due to Tait’s reductions. Long ago P. G. Tait showed that instead of coloring the nodes of a planar graph, equivalently one can color the edges of bridgeless cubic planar graph with three colors. We have also given an independent proof of this conjecture, that is without using four color theorem by defining and using spiral chains in the cubic planar graphs.

Last idea historically is the oldest, most elegant and most striking one [4],[5]. I call it this “easy to understand hard accept” type proof.  But it is true and is based on the Kempe’s  inductive proof. Historical fallacious inductive proof of Kempe have been re-considered by many mathematicians whether it could be repaired. All attempts so far have been either modification of Kempe color switching argument or trying to show that random second-time coloring would not produce an impasse. We have given double spiral chain coloring method when Kempe's argument fails by the trap of the incomplete four-coloring that there is always a simple re-coloring of the nodes of a planar graph so that the undecided node colored properly. Hence our method may be considered as an completion of fallacious Kempe's inductive proof.

 

Text Box: (Outline)
Proof  (A):   Spiral Chain  Node Coloring 

Ø	Input:  Any maximal planar graph.
Ø	Construct of spiral chains of the graphs.
Ø	Three color of each spiral-segment of the spiral chain using safe colors.
Ø	Output: Is the four color of any maximal planar graph.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

SPIRAL CHAIN COLORING: DIRECT PROOF

 

 

 

Spiral chains can be obtained easily by selecting edges one by one of the maximal planar graph starting from a vertex in the outer cycle and get into the inner vertices in all clock-wise (or counterclock-wise) direction. Since the number of outercycle vertices of a maximal planar graph is three there are exactly six spiral chains.  

 

Spiral segment.  A spiral segment Si of S is a sequence of vertices   such that , where k1  and vk is the first such node  in .

 

Throughout paper we denote the four colors by  C={B, R, Y, G}={Blue, Red, Yellow, Green}.

 

We begin with the normal maps shown in Fig. 1(a) and (b) respectively with 9  and  14 regions (including the outer-region). Here the term normal is being used to indicate that no more than three regions meeting at one point. One of the property of these maps are that the corresponding planar graphs are maximal i.e., faces in the planar graph are all triangle. 

 

 

 

 

 

 

Fig. 1 Maps, spirals and four coloring.

 

 

 

Let us give some intuitive arguments about the use of spiral-chains in the coloring of graphs. One of the unwanted task in any graph coloring algorithm is the backtracking. That is if at any stage we cannot find free proper color in the k colors and we need to use (k+1)th color in the k-chromatic graph, in other words  the coloring algorithm should restart in worst right from the beginning  or from some previous step and try to overcome this impasse by coloring the nodes in another way. On the other hand spiral chain in the maximal planar graph can be considered as a road-map in the coloring algorithm. In general a node in the spiral chain  looks like a way to "cut up" a graph so that each node  is connected to one of  four kinds of  vertices: one node  forward of it in the spiral, and one node  behind it, and then a set of nodes  to its "right" which are bisected by the chain, and another set on the "left" which are bisected on the other side.  Consider now any pairwise neighbor three sub-spiral chains , in G such that nodes of  (right sub-chain)  have already been colored completely, nodes  of  (middle sub-chain) colored partially till the vertex x and all vertices of   (left sub-chain) have not yet been colored. In the spiral chain coloring algorithm in deciding the color C={B, R, Y, G} of the node  x we need only to consider the color of the node  y on  with  and the color of the nodes  adjacent at x on . In another words while coloring the current node  x we only need to  consider the nodes of right-spiral chain and the color of the vertex  y.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

              

 

 

 

 

(a)

        

 

(b)

 

Fig. 2  Spiral-chain coloring of  the map in Fig. 1(a)  and the four color of the graph corresponding simplified map of  Martin Gardner’s (1975) April Fool’s joke (see Fig. 1b).

 

Example 1. Consider the maximal planar graph shown in Figure 2 (a) which its core is an empty graph. Spiral segment S1 is a path of length two which necessarily forms a triangle in G and we color its nodes as R, G, B. Hence the color class of S1 is .  Next spiral segment S2 surrounds S1 so we have to switch color class C1 to . Now the color green GÎC becomes a safe color with respect to C1 since  and color red RÎC becomes a safe color with respect to C2 since RÏC2.  Next we will argue how to color spiral segments. Let v be any node of Si, i≥2 which has not yet been colored. For i=1 we don’t put any rules on the node coloring of  S1  except we say that any 3-coloring will do the job.

 

Example 2.  Consider the maximal planar graph shown in Figure 2 (b) which its core is a single node. One of its spiral chain S can be easily obtained by starting any outer vertex, say from the node  v9 and selecting nodes in decreasing order. That is V(S)={v9,v8,…,v1} and here V(S)=V(G) since spiral chain S is also an hamiltonian path. Spiral segments of S are S1={v1,v2,v3} since v3 is the first vertex closing the segment into cycle with the vertex v1, S2={v4,v5,v6,v7,v8} since v8 is the first vertex closing the segment into cycle with the vertex v4 and finally S3={v9} is the spiral segment without an edge. Three-color classes, the use of safe colors have been shown in the figure.

 

Fig 1(a) and (b) illustrate spiral chain coloring algorithm on the maps.

 

 

Node Coloring Rule (NCR)

While three coloring nodes  of a spiral-segment, use  non-safe colors whenever it is possible.

 

 

Note that at beginning since we start with the 3-coloring of the first spiral segment we do not know its safe color till we color the nodes of the next spiral segment of the spiral-chain.

 

The following Lemma accounts the main step towards the non-computer proof of the four color theorem [6].

 

Lemma 1. If the nodes  of a spiral chain are all colored by the NCR then

(a) we do not need any re-coloring of the vertices and furthermore

(a) we do not need the fifth color.

 

In case of the maximal planar graph has more than one spiral chains nothing much changed in the spiral-chain coloring algorithm. Note that since each spiral segment is 3-colorable we are left one free color for the last outer node on the spiral chain. This will assure the termination condition of the coloring algorithm.  

 

Text Box: (Outline)
Proof (B): Spiral-chain Edge Coloring

Ø	Input: Graph is a cubic bridgeless planar graph.
Ø	Construct spiral-chains (comb-tree) of the graph.
Ø	Color the edges of the spiral chains using three colors and selecting one of the color as the “primary” color. While coloring edges if there is color-conflict resolve it by using backward Kempe-color switching.
Ø	Output: Three-edge coloring of the graph.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

SPIRAL-CHAIN TAIT’S COLORING: INDIRECT PROOF

 

 

    Assuming the four color theorem (4CT) it is easy to show that every cubic (bridgeless) planar graph has a three-edge-coloring since Tait found an equivalent formulation of the 4CT in terms of 3-edge-coloring. Here is the proof.

 

Assume that the regions of a cubic planar graphs colored properly by red (R), blue (B), green (G) and yellow (Y) colors. Then if two neighbor regions are colored by RG or GY then color its boarder (edge in the cubic graph) by G, if two neighbor regions are colored by RG or BY then color it boarder by R and if two neighbor regions are colored by RY or BG then color its boarder by B.

 

Three edge coloring of cubic planar graphs  is an old-conjecture due to Tait in the squeal of  efforts in settling the four-color conjecture at the end of the 19th century. Here we will outline an independent proof of this famous conjecture. Again the proof is rely on the spiral-chain coloring but rather on the coloring of the edges of a cubic bridgeless planar graphs [13]. In [13] we have first shown that any cubic planar graph can be decomposed into vertex disjoint spiral chains which in turn expressed as the union of folded special spiral caterpillar (spiral-combs). Then based on the spiral-comb(s) decomposition we have provided a simple three-edge-coloring algorithm for any given cubic planar graph. In the second part we have shown that the same method can also be applied to a similar but more general three-edge cubic graph (non-planar) coloring conjecture of Tutte which has been recently settled by a series lengthy papers using the classical four color theorem proof technique. That is

 

Conjecture. Every 2-connected cubic graph with no Petersen minor is 3-edge colorable.

 

    This extends the four color theorem as Tait showed that the four color theorem is equivalent to the statement that every planar 2-connected cubic graph is 3-edge colorable. It also implies that certain non-planar graphs are 3-edge colorable. Let us say that G is apex if Gv is planar for some v and G is doublecross if it can be drawn in the plane with crossings, but with atmost two crossings and with all the crossings on the boundary of the finite region. Both apex and doublecross graphs have no Petersen minor so Tutte's conjecture implies:

 

Conjecture (RST). (1) Every 2-connected apex cubic graph is 3-edge colorable and (2) every 2-connected doublecross cubic graph is 3-edge colorable.

 

    Tutte and RST equivalences has been shown in [6] that "a minimum counter-example" mean a 2-connected cubic graph G with no Petersen minor which is not 3-edge colorable, with  |V(G)| minimum. That is every minimum counter-example is either apex or doublecross. Eventually Tutte's conjecture has been settled by a series of papers [6]-[10] by using the classical proof method of the four color theorem [12],[13],[14].

 

    In this section we will give an three edge-coloring algorithm which uses spiral chains of the given cubic bridgeless planar graph. Let  C={R,O,G}. In the figures we use numbers 1,2,3 on the edges instead of letters to avoid confusion. Let S be denote a spiral-chain of G. As we go through the vertices of S we construct a path Ps with nodes v,v,...,vk and assume that V(P)=V(G),i.e., k=n. We will investigate cubic graphs with several spiral-chains later. Edges incident to Ps together with the edges E(Ps) of the path constitute a comb-caterpillar tree Cs(Vs,Es), where Vs={v,v,...,vk} and Es=E(Ps){E(Ps): {vi,vj} vi,vjV(Ps) and d(vi,vj)≥2}. An edge b of the Cs is called the backbone-edge if  bE(Ps) and is called the hair-edge h if hE(Ps) . It is clear that Cs=G but some of the edges of E(Ps) are counted twice since any hair-edge of Cs has two ends in the spiral-chain S. Again as we go through the edges of S we call that hair edge hE(Ps) is real if it is encountered for the first-time and imaginary if it is encountered for the second-time. In the figures all the real-hair edges have been shown in straight-lines while the imaginary-hair edges are shown with dashed-lines. The importance of the real and imaginary hairs will be clearer when deciding the color of the current edge in the spiral chain. We have classify the colors into two classes. The color green G is called as the "primary" color while the colors orange O and red R are called the "secondary" colors. In the coloring algorithm given below primary color G is used mostly for the spiral-chain backbone edges and the secondary colors O and  R are used mostly for the hair-edges.

   

    Algorithm A.  Spiral-chain edge-coloring (for single spiral-chain)

    Let the cubic planar graph G be drawn in plane without any crossings. As the first step construct in clockwise direction a spiral-chain S of G starting from a vertex v of its outer-boundary cycle. Let Cs be the corresponding comb of S. Start coloring the edges of the backbone edges of Cs alternatingly by green and orange colors i.e., (G,O)-chain and the hair edges of Cs by the red R color.  If all vertices of S is covered and edges incident to vertices are properly colored by G,O, and R then the coloring is the desired proper three edge-coloring.

    a) If for some backbone edge ei=(vi,vi-1) is forced to be colored by R  because of the color (it must be orange O  since G is primary color) of the hair hi-1 at vi-1. Furthermore if the hair hi had been colored by R before then both ei and hi would be R. In this case there must be a node vj, with j>i and a spiral sub-path P(vr,vs), with s>r<j>i. But the path P(vi,vj)=(vi,vr) P(vr,vs)(vs,vj) is a (R,O)-Kempe chain, where (vi,vr) and (vs,vj) are the hair-edges. Therefore we perform Kempe-chain color switching for the edges of P(vi,vj) and resolves the problem at vertex vi.

    b) If for some backbone edge ei=(vi,vi-1) is forced to be colored by O because of the color of the hair hi-1 at vi-1. Furthermore if the hair hi had been colored by O before then both ei and hi would be O. In this case there must be a node vj, with j>i and a spiral sub-path P(vr,vs), with s>r<j>i. But the path P(vi,vj)=(vi,vr) P(vr,vs)(vs,vj) is a (O,G)-Kempe chain. Therefore we perform Kempe-chain color switching for the edges of P(vi,vj) and resolves the problem at node vi.

 

    That is in critical cases we have always suitable Kempe-chain with both ends are hairs of the spiral comb-tree. Hence we can perform Kempe-chain color switching within the spiral-chain of G when we needed to resolve color duplication at node vi.This argument is also valid at the termination of the algorithm. That is let x be the last node in the spiral chain S. Then the hairs (z,x)S and (t,x)S that have already been colored properly before, from the point view of the nodes  z and t. Consider the last edge (y,x)S. Now if (z,x) and (t,x) have been colored with orange and red and we can color the current edge (y,x) of S then spiral-three-edge coloring ends properly. But if (y,x) is forced to be colored by orange or red because of the coloring condition at the vertex adjacent x in S then there must be (orange-green)-Kempe chain (respectively (red-green)-Kempe-chain) start with the orange hair (respectively red hair-edge) at x and end at some node x. So we perform Kempe-chain switching and resolve the conflict at the node x. It can be seen that applicability of Kempe-chain switching rely on the selection of color "green" as the primary color. That is this time our rule is “use the primary color on the spiral chain edges whenever possible”.

    Fig. 3 and Fig. 4  illustrate the spiral-chain edge-coloring algorithm.

    Algorithm A can be easily modified to cubic planar graphs having more than one spiral chains. In this case if the current node, say va of spiral-chain Si adjacent to two nodes  vb,vc that have already been contained in Si before or in some other spiral-chain Sj,j<i then we cannot go further. Hence we select closest new node incident Sk,k=1,2,..,i and start new spiral-chain Si+1 from that node. When all nodes of G covered we obtain node disjoint set of spiral-chains S,S,...,Sm. Note that some of spiral-chains degenerate to a single node. One can easily notice that spiral-chains S,S,...,Sm are topologically nested in the plane. Now we are ready to give spiral-chain edge-coloring algorithm for this case:

   

    Algorithm B. Spiral-chain edge-coloring (for multiple spiral-chains).

    Let S,S,...,Sm be the set of spiral-chains of the cubic planar graph. Apply Algorithm A to each spiral-chain Si,i=1,2,...,m. Note that for each application of Algorithm A we select always the color "green"  G as the primary color. This selection would minimize execution of number of the steps (a) and (b) in Algorithm A. That is it will color in green, maximum number of the backbone edges in the spiral-chains.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 3.  Illustration of the three-edge spiral chain coloring algorithm.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 4.  Tutte graph and spiral three edge coloring.

 

 

 

 

 

 



 

 

 

 

 

 

 

 

 

 

 

 

 



 

 

Text Box: (Outline)
Proof (C):  Kempe’s Argument Corrected

Ø	Input: Graph is an “bad-example” to Kempe’s argument i.e., incomplete four coloring.
Ø	Select suitable node v adjacent to undecided node u.
Ø	Use the “joker color” instead of the color of v.
Ø	Color of the node u is the previous color of v.
Ø	Start from node u and v by using all possible Kempe-color switching enlarge the length of  (B,Y) and (R,G)-Kempe chains.
Ø	Output:  Is a double-spiral chain of the graph  i.e., (B,Y)-Kempe chain and (R,G)-Kempe chain. 
           

 

 

 

 

 

 

 

 

 

 

DOUBLE-SPIRAL CHAIN:

KEMPE’S INDUCTIVE PROOF

 

 

    Most of the mathematicians agree in that bad (counter-) examples e.g., Heawood [7], de la Vallée-Poussin [11], Errera [9,10], Kitell [12] -graphs are rare and it is well-known that why Kempe's method would not work under these examples.  Errera example is more elegant than Heawood's example since requires that all nodes but one be precolored [9, 10]. Therefore we have chosen first a simplified version of Heawood example and then Errera example in our study. But to the best of my knowledge no one has come up with an answer of "how we can repair Kempe's proof without going into the classic proof of the four color theorem"? Although Wagon [13] , Hutchinson and Wagon [14] have studied possible answer of an similar question, by using Kittell's random color switching in order resolves the impasse in the Errera graph.

 

John Conway once said:

"I did read a few of the papers from this period, including Kempe's proof, Tait's deduction of his edge-coloring criterion from it, and an article in which Heawood pointed out the mistake, among other things, and the impression I got from them was much the same as Jim's. There was indeed a fair amount of interest in Kempe's "theorem", but not much evidence that any great number of people actually scrutinized his proof, or even read it. I don't think it would have made much difference if they had. The proof is very convincing, and in the days when the amateur provers were still interested in 4CT (Four Color Theorem), 2 times out of 3 "Kempe's Catastrophe", as Tom O'Beirne used to call it, was the proof they'd produce. Tom had a set lecture in which he gave Kempe's proof, illustrated by a specially made-up board with colored pegs, and seldom could anyone in the audience find anything wrong with it."

 

    Next we will consider the simplified Heawood bad-example. Consider the graph G with 9 nodes shown in Fig. 5  with node coloring, where overlap circles denote color switching. Initially  the node in the center of cycle of length five, C5, the big-white half-circle below the big-yellow (e.g., half-white-yellow twin) node is undecided since C5 have been colored with colors Y,B,R,B,G. Since there are two Kempe-chains; one (G,R)-Kempe chain (red-dashed lines) and other (Y,R)-Kempe chain so we can switch the colors green and blue nodes on the left-side and blue and yellow nodes on the right-side node-pairs. Then the colors of cycle C5 would be {Y,G,R,Y,G} and freeing the color "blue" to the undecided-node. But then we have c′(va)=c′(vb)=B, an impasse. This simple example was the source of the long story of the four color problem.

Before we discuss our solution for this problem we will give some observations that differs from the others.

 

·        Since the six possible Kempe-chains are RG,RG,RY,BG,BY,GY-types, if we increase the length of one of Kempe-chain, say (RG)-chain, by suitable color switching then the length of a (BY)-chain would also increases or remain same.

·        Maximum possible length of a Kempe-chain on C5 is three.

·        In case of an impasse, instead of switching node colors randomly, assign a new color (not a fifth color) to suitable existing node- color on C5  so that we can increase the length of Kempe-chain on C5. We call this new color in the incomplete precolored graph as "joker" color shown as nodes with star in Fig. 5 and 8(a). That is we have changed the number of colors in the color classes.

 

    Let us return to our bad example. We have chosen the joker color as "blue" and assign it yellow node of C5 i.e., half-yellow-blue twin node in the Figure 5. Now we have improper coloring of C5 since its colors are B,B,R,B,G. Then we use Kempe-switching to the middle three node colors B,R,B (see Fig.5) so that we obtain new proper three coloring of  C5 as  B,R,B,R,G. The impasse is resolved therefore assign yellow color to the center node. In Fig. 5 we have shown our final four coloring of G which consisted of two node-disjoint (R,B)-chain (thick blue-line) and (Y,G)-chain (thick red-line). Note that in the final four coloring of the graph the length of (R,B)-chain is increased to 4.  We will say more about the shape (double-spiral) of these two disjoint chains in the next section.

    In Fig. 6 we have shown double-spiral chains decomposition together with its four coloring of the original "bad-example" designed by Heawood  against for the Kempe-argument. It can easily be checked that the undecided region (with question mark in the figure) cannot be colored by B,R,G, or Y by using any Kempe chain switching operations. We note that while (B,G)-Kempe chain in the Heawood's map corresponds to a single connected acyclic graph (shown in dashed line) the others disjoint, that is two disjoint (R,Y)-Kempe chains. This is the main reason of the impasse. However by assigning a de-facto "joker" color instead of existing region color arround the undecided region, say R,  and performing Kempe-chain switching it is possible to glue the two (R,Y)-chains. Clearly this would resolves the impasse. In Fig. 5(b) we have shown the final four coloring on the corresponding maximal planar graph which is again is in the forum of double-spiral chains.

 

Excellent survey on the Kempe's method together with the detailed account of Errera's bad-example has been given by Hutchinson and Wagon [14].  We have re-drawn Errera graph, with its incomplete four coloring, by placing the undecided node  u (big white circle) at the central location of the graph in Fig. 7. That is the node u is clearly visible as the center of the wheel. We first note that the undecided node u is surrounded by the cycle C5 and colored with Y,B,G,R,G. Furthermore G,R,G-nodes of C5 are also in the (R,G)-chain (close-chain or cycle of length six shown in thick-line in Figure 7). Now the impasse can be resolved by the following steps:

 

- Apply Kempe-switching to the (R,B)-close chain.

- Select the "red" color as the joker-color and change blue-node in C5 to red. Then color of C5 becomes Y,R,R,G,R. Assign the color blue to the undecided node u.

- Since the colors of the nodes in C5 is improper we apply Kempe-switching first to (R,Y)-chain 1 (shown in green-dashed lines in Fig.8) and then to (B,R)-chain 2 (shown in grey-dashed lines in Fig. 8). Now we have Y,R,Y,G,R for the cycle C5 which creates another improper coloring outside the C5 (red edge in Fig. 8). We resolve this by enlarging the length of (Y,R)-chain by applying Kempe-switching to (Y,R)-chain 3. Now the impasse is resolved.

 

    Final four-coloring of Errera graph is shown in Fig. 8(b) together with its disjoint double-spiral Kempe chains. It is not difficult to see that for any bad-example to Kempe's method by using the joker color on  C5 and enlarging, say (Y,R)-chain by suitable Kempe switching results proper four coloring of the whole maximal planar graph. It is not difficult to see that for any given bad-example for the Kempe-method, by selecting suitable "joker" color and enlarging the Kempe chain result a proper four coloring in the form of double-spiral chains.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 5. Simplified Heawood bad-example and double-spiral solution.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 6. Heawood map and double-spiral coloring.

 

 

 

           

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 7.  Errera’s incomplete four coloring.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig. 8. Errera’s incomplete four coloring and its double-spiral solution.

 

 

 

 

 

 

 

 

CONCLUSION

 

 

Four color problem has been agenda of the mathematicians not only because of  it’s  lengthy computer aided proofs  but also its puzzle-like character i.e., “show me if you can color it by using only four colors”. Our main contribution to the solution of this mathematical enigma is to provide the right tool or the key that is spiral chains in graphs or maps. It is this tool that enable us to show that the “four color puzzle” is not different than the solution of the any other solveable puzzle.  We hope that at least in the future the spiral-chain coloring  solution  would  replace the positions of the existing classical solutions. Now the big question remains to be answered, is the next similar problem with respect to the solution methodology  waiting in the line. Is there a non-computer proof of the Kepler sphere packing conjecture? Who knows may be a kind of spiral chain  traversing the centers of the face-centered cubic packing of spheres could be used.  Time will show us whether this would be the case or not,  but as today  we have to be satisfied  with the existing  proof  [3],[17].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

References

 

[1]  K. Appel and W. Haken, “Every Planar Map is Four Colorable”, Contemporary Math., 98, 1989.

 

[2]  G. Gonthier, “The Four Color Theorem in Coq”, in Types 2004 Conference, December 17, 2004, Thales, France. (http://research.microsoft.com/~gonthier/4colproof.pdf)

 

[3]  T. Hales, “FLYSPECK: Towards a Formal Proof of the Kepler Conjecture”, in Types 2004 Conference, December 17, 2004, Thales, France.

 

[4] A. B. Kempe, "On the geographical problem of the four colours", American J. of Math., 2(3), 193-200, 1879.

 

[5]  B. Mohar, "Kempe equivalances of colorings" preprint, January 2005.

 3 : K. Appel and W. Haken, "Every planar map is four colorable", Contemporary Math., 98, 1989.

 

[6] N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, "The four colour theorem", J. Combin. Theory Ser. B., 70 (1997), 2-44.

 

[7]  J. P. Heawood, "On the four-color map problem", Quart. J. Pure Math., 29 (1898), 270-285.

 

[8]  I. Cahit, "Spiral chains: A new proof of the four color theorem", preprint arXiv.math.CO/0408247, 18 August 2004.

 

[9] A. Errera, "Du colorage des cartes et de quelques questions d'anaysis situs", Thesis, Gauthier-Villars, Paris, 1921,66pp.

 

[10]  A. Errera, "Exposé historique de problème des quatre couleurs", Periodico di Matematische, 7 (1927) 20-40.

 

[11]  de la Vallée-Poussin, Interm. Math. 3, 179-180, Paris, 1896.

 

[12]  I. Kittell, "A group of operations on a partially colored map", Bull. Amer. Math. Soc., 41 (1935) 407-413.

 

[13] S. Wagon, "A machine resolution of a four-color hoax", CCCG 2002, 174-185.

 

[14] J. Hutchinson and S. Wagon, "Kempe revisited", Amer. Math. Monthly 105 (1998) 170-174.

 

[15]  I. Cahit, "Spiral chains:The proofs of Tait's and Tutte's three-edge-coloring conjectures", preprint arXiv.math.CO/0507127 v1, 6 July 2005.

 

[16] I. Cahit, “The Four Color Map Theorem: Kempe’s Fallacious Proof Repaired”, preprint, September 2005.

 

[17] T. C.  Hales, “A Proof of the Kepler Conjecture (DCG Version)”, March 13, 2004, http:// www.math.pitt.edu/~thales/kepler04/fullkepler.pdf

 

[18]  R. Thomas, “An Update on the Four-Color Theorem”, Notices Amer. Math. Soc., 45(7), 1998, 848-857.

 

 

 

 

 

 

 

 

 

October 4, 2005