On Geometrical Methods that Provide a Short Proof of Four Color Theorem

BAHMAN MASHOOD

American Journal of Mathematical Analysis

On Geometrical Methods that Provide a Short Proof of Four Color Theorem

BAHMAN MASHOOD

La Playa Street. 304. San Francisco.CA 94109, US

Abstract

In this article we introduce a short and comprehensive proof of four color theorem based on geometrical methods. At the end of the article we will provide a short proof of the De Bruijn Erdos theorem for locally finite infinite graphs.

Cite this article:

  • BAHMAN MASHOOD. On Geometrical Methods that Provide a Short Proof of Four Color Theorem. American Journal of Mathematical Analysis. Vol. 3, No. 3, 2015, pp 65-71. http://pubs.sciepub.com/ajma/3/3/2
  • MASHOOD, BAHMAN. "On Geometrical Methods that Provide a Short Proof of Four Color Theorem." American Journal of Mathematical Analysis 3.3 (2015): 65-71.
  • MASHOOD, B. (2015). On Geometrical Methods that Provide a Short Proof of Four Color Theorem. American Journal of Mathematical Analysis, 3(3), 65-71.
  • MASHOOD, BAHMAN. "On Geometrical Methods that Provide a Short Proof of Four Color Theorem." American Journal of Mathematical Analysis 3, no. 3 (2015): 65-71.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction and Preliminaries

The Four Color Theorem is well known in the mathematical community. It states that any number of connected locally connected regions located in the plane (i.e' they are all subsets of R2), intersecting only on their common boundaries, can be separated by four colors. In order to present a coherent mathematical view of the above theorem we need to state the following definitions and use the basic concepts and facts in topology. For more details on the basic concepts in topology we recommend the book, Topology (1970) by James Dugundji. Throughout this article the paths and closed curves are subsets of finite a graphs hence we use a type of digital geometry to prove some of the arguments. But many of the lemmas and theorems are stated and proved in the most general cases. The Jordan closed curve theorem as stated at [2] is the basis for many of the lemmas and theorems. When dealing with closed curves and paths we define the interior path of the given closed curve to be paths that except one or two points on the boundary the rest of the path lives in the interior of the closed curve. For a connected Graph G, its spectrum, spect(G) is the operator norm of the adjacency matrix. We say that two connected graphs G1 and G2 are equivalent, G1 ~ G2, if their corresponding adjacency matrix are unitary equivalent. this concept is used to define some useful definitions that will help proving the main theorem, theorem (2.21). the paths are all directed in same way. For example the paths located on closed curves have the same direction as the direction on the closed curve which is clockwise direction. Many of the sets we are going to deal with are connected, closed and bounded. These kinds of sets constitute a very important class of sets.

Definition 1.1 A compact connected subspace of a Hausdorf metric space is called continuum.

In particular here by region we mean locally connected continuum sub-set of R2. To state equivalent version of four color theorem represent each of the regions by a vertex in R2 and connect two points if and only if the corresponding regions intersect. This will provide us with a graph G. Now the four color theorem can be expressed equivalently to this situation as to associate a color to each of the vertices in such a way that no two vertices connected by an arc can have the same color. Note that without loss of generality we can assume that the above graphs are connected. In fact throughout this article all the graphs are connected. For a set R2, let Qc be the complement of Q in R2, ie, Qc = (x R2, x not in Q). Also we denote the interior of Q by int(Q) In final part of this article we are going to deal with locally finite infinite graphs. These are infinite graphs with the property that each vertex is connected to finitely many other vertices. For a set Q, we set Card(Q) to be equal to the cardinality of the set Q. So by our definition any two region A2 and A2 from the collection are either disjoint or (A1) (A2) = (Bound(A1)Bound(A2) In the later case A1 and A2 have to take different colors. Finally by Jordan closed curve theorem S divides the space in two regions, where one of the regions SC S can be be mapped homeomorphically onto the closed disc corresponding to a circle. For simplifying the notation we write int(S) instead of writing int(SC).

The following definitions are well known

Definition 1.2 A subset of S R2 which is homeomorphic to a cicle is called closed curve. The above homeomorphism can be chosen so that can be extended to the homeomorphism taking SC = Sint(S) onto the closed disc that corresponds to the above circle.

Similarly the the edge or the arc connecting two vertices of a graph is homeomorphic to a closed interval. A path is a sub continuum of which is the union of number of arcs. It is clear that the path is also homeomorphic to a closed interval. Suppose S is a closed curve which is the subset of a connected graph G. Let us adopt the following notations.

Definition 1.3 Given a connected graph G, we denote the set of its vertices by V (G)), the number of its vertices by n(G), and the set of its edges by E(G). Suppose S G be a closed curve. We set SCG = SCG and SCintG, to be equal to the set SCG minus E(G) ie' SCintG = SCG(E(G))c.

Note that the set SCintG is not necessarily a connected set. Let G be a connected graph and suppose be the set of all vertices of G. Furthermore for the vertices located on a closed curve S G the sequence of vertices have clockwise orientation, ie' is located to the right of . and are called neighbouring vertices if they are connected by an edge in V(G).

Definition 1.4 For a given connected graph G, The function f from V(G) to the set (1,2,3,4) is called colorization if for any two neighboring vertices and ,

Definition 1.5 Following the same notations as in the above we define Cl(G), to be the set of all colorizations for G.

For any two points x,y G, let d(x,y) be the usual Euclidean distance of x from y in . Let us set the following notations, d(x,G) = min(d(x,y), y G) and d(G) =max(d(x,y), x, yG). For each x G let D(x,d(x,G)) be equal to the closed Disk with the center in x and radius d(x,G). Let us define Then it is easy to check that D(G) is a closed set containing G.

Definition 1.6 Keeping the same notations as in the above, the vertex x G is called to belong to the exterior boundary of G, denoted by EBound(G), if x can be connected via a path in R2 (G)c to any point in D(G)c =R2 - D(G) = ((y R2), y not in D(G)).

In the following arguments in order to shorten the notations for a given closed curve S we write int(S) instead of int(SC).

Definition 1.7 Keeping the same notations as in the above, The closed curve S G is called maximal closed curve if and only if S EBound(G). It is called max closed curve if given some other closed curve , with int() int(S), then = S.

Suppose S is a closed curve, . Now let be number of vertices on , where xi can be reached from moving clockwise on encounter once we move from xi to including the two end points. By we mean the set of all the vertices of that we encounter once we move from to excluding the two end points. Note that since we are moving clockwise on the closed curve we have the following identifications, and so on. Note that moving clock wise along S, the intervals , (respectively ) are well defined only if Suppose be the set of all the vertices on S moving clockwise on S. Then for each integer the vertices and are called neighbouring vertices. Note that S is a metric space with the metric inherited from . Given two points where is to the right side of (ie' moving clockwise from we reach ), we set an order . the closed and open intervals on the closed curve S have the same definition as the ones on real line, just with the points belong to S, ie, and In order to identify the intervals on S clearly, we let the set to take their indices from the well known ring The following theorem is going to be used throughout the rest of the article.

Theorem 1.8 Keeping the same notations as in the above, two max closed curves that are subsets of G can not intersect in more than one point,

Proof Suppose and are are max closed curves that are subset of G. Let us give clockwise orientation to the above closed curves. Since and are not equal there exits a point x in not belonging to . Moving from point x along clockwise suppose intersect at vertices and . With the first vertex on that will encounter and the last one. Now consider the paths, and It is clear that the union of these three, paths is a closed curve. In order to prove the theorem it is enough to show the following condition, holds. We call the above condition the U-condition. Let and w be a point in For U-condition to hold it is enough to show that any path s connecting v to w will intersect . To complete the proof we need to prove the following lemmas.

Lemma 1.8.1 Keeping the above notations suppose then the U-condition holds. Futhermore contains .

Proof Let and Suppose s is a path connecting to . Then s has to intersect the boundary of . Hence s either hits or it hits Suppose in its way to v it hits for the last time at point Now using the fact that at point y, s either enters the interior of or enters the interior of . In the first case it will hit before reaching v. In the second case it will hit before reaching v. This implies that thus the U-condition hold. Now we clam that To show that suppose Then for there exists a path But if x is in then must intersect . At this point the fact that does not intersects implies that

Definition 1.8.2 The encounter of the closed curves Si, i=1,2, as stated in the above lemma is called of type-I

Lemma 1.8.3 Keeping the above notations suppose that and S2 intersect only on two points and . Furthermore assume that moving clockwise from x on we enter the interior of S2 at and leave it at . Then the U-condition holds.

Proof Note, it is easy to see that moving clockwise on S2 it will enter the interior of at and leave it at . Let us consider the following paths. and Next define the closed curve Considering and S4, note that This using lemma 1.8.1 implies that Similarly we can show that and this complete the proof.

Definition 1.8.4 The encounter of the closed curves Si, i= 1,2, as stated in the above lemma is called of type-II.

Lemma 1.8.5 Keeping the above notations suppose that and S2 intersect only on two points and . Furthermore suppose Then the U-condition holds

Proof Let us define the closed curves S4 and S5, S4 being equal to the union of and S5 being equal to the union of and It is easy to see that hence by the above lemma Where the directions of paths on Si, i= 1,2 are the clockwise directions on Si. Since by lemma 1.8.1, and this complete the proof

Definition 1.8.6 The encounter of the closed curves Si, i=1,2, as stated in the above lemma is called of type-III

In general following the same procedure as in the above moving clockwise on from , suppose intersect S2 first time at and last time at . Then let us define the closed curve S3, to be equal to the union of and Now set to be equal to the union of and But Thus since the encounter of and is of type-I. Hence by lemma 1.8.1 similarly we can show that and this complete the proof of theorem 1.8.

Lemma 1.9 Suppose is a closed curved which is the subset of a connected graph G. Then there exist a max closed curve , such that contains

Proof For a given closed curve if then we replace by S2. Next Using lemma 1.8 if intersect another closed curve in more than two points, then by the above arguments there exits another closed curve such that Now proceed inductively, after finite number of steps we will end up having a closed curve , such that if S intersects any other closed curve at more than one point then Further more if is any other closed curves with then

Theorem 1.10 Let G be a connected graph. Then the exist a set of max closed curves and paths such that G is equal to the union of the above paths and the set Q, Furthermore

Proof In order to prove the above theorem we need the following definition and lemma

Let us consider a max closed curve , with G a connected graph. Suppose we have a sequence of max closed curves , Suppose for each is connected to , via a path in G.

Definition 1.11 Keeping the same notation as in the above. The sequence of closed curves (Si), i = 2,3, …, n are called descenders of S1.

Lemma 1.12 Keeping the same notation as in the above, Let , i =1.2.3,.. be a sequence of max closed curves. Then the above max curves can be connected to each other only by unique path s G. Furthermore if S2 and S3 are both connected to S1 via paths in G, then S2 and S3 or any of their descenders can not be connected to each other via paths in G.

Proof Follows from the definiton of max closed curves and the arguments of lemma 1.8.

Note that the above statements holds if we consider the vertices of the paths connecting the max closed curves as max closed curves. In particular if we retract each one of the max closed curves to a point the resulting will be a tree.

Finally theorem 3.22 implies that any one of max closed curve or corresponding connecting paths between them are subset of EBound(G). But by theorem(1.10) any vertex of is either a member of for some max closed curve or is a vertex on one of the paths connecting two max closed curves and . This complete the proof of theorem 1.10.

The following lemmas can be verified immediately therefore we skip the proofs.

Lemma 1.13 Keeping the same notations as before. Given a path , then the vertices on s can be separated by using two colors.

Lemma 1.14 Given a closed curve , with G a connected graph. Then if the number of vertices on S, is even then the vertices on S can be separated by two colors. Otherwise three color would be sufficient to separate all the vertices on S.

At this point suppose That G is a connected graph and be a max closed curve. Now let be another closed curve with and such that Then G is equal to the union of and S1. Assuming that G is located on the surface of an sphere implies that there exists another connected graph G1 ~ G such that S1 is max closed curve in G1. We denote S1 a semi max close curve.

Definition 1.15 We say a connected graph G has property R. if there exist a colorization such that on every semi max closed curve

Now it is clear to see that if G1 is a connected graph with property R and G2 another connected graph such that G1 ~ G2, then G2 has property R too. Next let G be a connected graph and a closed curve. Let be a sequence of all the vertices on S.

Definition 1.16 Let . Given a path connecting to. Now consider the closed curve that is the union of and We call the path s reducible if there exists another internal path , between two different points , such that for the closed curve is a proper subset of . Otherwise s is called irreducible. suppose there exist two vertices and irreducible path in , connecting to . If we say S is of type-I. Otherwise if j = i + 1, we say S is of type-II. If S is not of type-I or type-II, we say S is of type-III.

Lemma 1.17 Given a closed curve with G a connected graph. Let , be the set of vertices of S moving clockwise on S. Suppose there exists a vertex such that the connected component of that contains and does not contains any edges in S, contains another vertex then there exits an irreducible path in connecting to a vertex

Proof If a connected component as in the above contains and another vertex then by the fact that is connected graph too, we have a path that connect to . Then it is clear that there exits a vertex and irreducible path connecting to a vertex

At this point we are going to introduce an special subset G a connected graph. We impose ordering on by Г (,) ≤ (x,) Г if and . It is easy to see that ≤ is partial ordering on Г. Now using the fact that for every integer k the set spect(k) = (spect(G), G a connected graph and n(G) = k) is a finite set, we can order the above set by the magnitude of its members. Hence set . Where for i > j, ri> rj, r1 = lower bound(spect(k)) = upper bound(spect(k). Also to facilitate our notations for a closed curve S G we replace Cl(SCG) by Cl(S).

Lemma 1.18 Let and S2 be subsets of connected graph G both being max closed curves. Suppose the above two closed curves are connected by a path s G or a common vertex q and that they have colorizations , i = 1,2. Let us de_ne connected graph Then There exists a colorization extending or

Proof By lemma 1.12 Points on s can be separated by two colors, Thus can be extended to in an obvious way. Suppose the point is connected by an edge in s to the point c 6= b in s. If cl1(b) = i = cl2(b) = j then we are done. Otherwise if i ≠ j we define cl3 Cl(S2) by cl3(a) = i, if cl2(a) = j, cl3(a) = j, if cl2(a) = i or else cl3(a) = cl2(a). Now cl1 can be extended to G1 and we are done in this case. Finally If and S2 are connected by a common vertex q and cl1(q) = i = cl2(q) = j then we are done. Otherwise repeating the above arguments we can define a colorization cl3 on S2 ∪ = G1 and we are done.

At this point note that every connected subset the connected graph G is also a connected graph. As before we define an interior graph to be a subgraph of G that does not contain any element from the set E(G).

Theorem 1.19 Given a connected graph G Suppose every max close curve, S G has property R. Then G has a colorization.

Proof Suppose G is a connected graph and Let be the set of all max closed curves in G. Let be the set of all paths in G connecting max closed curves. Where some of these max closed curves consists of single vertex. Therefore by theorem 1.10 and lemma 1.12 we can assume that G is equal to the union of the max closed curves, the part of G they contain in their interior and the paths in G that connecting them. By lemma 1.12 there are unique pathes between the maximal closed curves and for any two maximal closed curve that are connected to a third one their descenders are not connected to each others via paths or common vertices. Now our assumption states that for any one of max closed curve S G, SCG has property R. Thus each of the maximal closed curves SjG has a colorization clj acting on SjCG. Next let us begin from the max closed curve S1 with a colorization cl1 S1C G and all max closed curves S1,r G that are connected to S1 by the paths s1,r G. For each of the max closed curves S1,r, set G1,r= Si,rCG∪s1,r. Now by lemma 1.12, we can extend cl1 to become a colorization on G2,r=S1CG∪G1,r. Now repeating the above process from each of the max closed curves S1,r, using lemma 1.18 we are going to extend cl1 to become a colorization on each of the descenders of S1 and ultimately after repeating the above process finitely many times we will get a colorization acting on G.

2. The Main Result

In this section we are going to state the main theorem and its proof.

Lemma 2.20 Suppose G is a connected graph and S a subset of G which is the max closed curve with SCG = G. Then S has property R.

Proof In order to prove the theorem we need to state and proof the following lemmas

Lemma 2.20.1 Keeping the same notations as in the above suppose S is of type-II. Then there are two vertices ai G(S), i = 1, 2 and an irreducible path s1 int(S) connecting the above two vertices. Furthermore there exist two connected graphs G1 and and G1 each containing a max closed curve, S1 G1, S1 G1, such that S1CG1 = G1 and S1CG1 = G1. Finally we have int(S) int(int(S1) int(S1) int(int(S1) and G ~ G1.

Proof Set then is a closed curve. Next we can construct a path connecting a1 to a2. Let and It is clear that is a max closed curve in G1 and S1CG1 = G1. Next following their constructions, int(S1) int(S1) and int(S) int(S1).

Before proceeding to the next lemma we need to bring the following definition

Definition 2.20.2 Let G1 and G2 be a connected graph and Si Gi, i = 1,2 be a max closed curves with SiCG = Gi, i=1,2. then we call Si a full closed curve. In particular if G1 ~ G2 then we write S1 ~ S2.

Lemma 2.20.3 Let S G be as in the above. Then S is either equivalent to type-I or to type-III closed curve.

Proof If S is type-I or type-III we are done. Otherwise following notations and arguments of lemma 2.20.1, consider the full closed curve S1 G1 and S1 G. G1 connected graph. We had S ~S1, int(S1) int(S1), V (S1) = V (s1) = V (G)s1, int(S) int(S1). Furthermore any path in the interior of S1 connecting to vertices of S1 lives in the interior of S1. Now if S1 is of type-I or type-III we are done, otherwise proceeding as in the above we have two closed curve S2 and S2 G with the following properties. S2 is a full max closed curve subset of a connected Graph G2 ~ G, int(S2) int(S2), int(S1) int(S2), int(S1) int(S2) and the interior paths connecting vertices of S2 live in the interior of S2. Proceeding by induction and because G is a finite graph after finitely many steps we get the sequence of closed curves, Si and Si 1 ≤ I ≤ m0 with the following properties. Si ~S, int(Si) int(Si), int(Si-1) int(Si) and such that any interior paths connecting the vertices of Si lives in the interior of Si. Hence by the fact that G is finite at some stage m0, either is of type-I or of type-III. The proof of the lemma is complete.

To complete the proof of the lemma we use induction on n(G). So suppose given an integer k such that the statement of lemma hold for all connected graph having only one max closed curve S with n(G) ≤ k. Lets a1,a2, …am be a set of all vertices on S G, where ai can be reached from ai1 moving clockwise on S. If all connected component of G intersect S at most at one point, ie, S is of type-III. In this case by lemma 1.14 we can construct a colorization cl Cl(S), cl(S) ≤ 3. Now we want to extend cl to become a colorization on all G. Since for each of the connected components Gi G, n(Gi) ≤ k, then by induction and theorem 1.19, Gi has property R. Now using lemma 1.18 we can extend cl to become a colorization for G thus G has property R. Otherwise by the above lemma 2.20.3 we can assume that S is of type-I. Hence for some vertex aj 2 S there exits an irreducible interior path s SCintG from aj to al, where aj and al vertices of S, moving clockwise on S with j + 1 <l. Therefore we will get a closed curve S1 G which is the union of s and the path [al,aj] S. Now note that S1CG is a connected graph with n(G1 = CG) = k. Hence by induction assumption G1 = S1CG has property R therefore there exists a colorization cl Cl(G1) such that Card(cl(S1)) ≤ 3. Now note that any connected component of G that contains a vertex in G[aj,al] S, does not intersect S at any other point. Hence using lemma 1.14 and lemma 1.18 we can extend cl to become a colorization on G with Card(cl(S)) ≤ 3. This complete the proof of lemma 2.20.

Theorem 2.21 every connected graph G, has property R thus has a colorization.

Proof By lemma 2.20 each one of max closed curves has property R. Finally Theorem 1.19 completes the proof.

Finally we are going to bring a short proof of De Bruijn Erdos theorem for locally finite infinite planar graphs

Theorem(De Bruijn Erdos) Suppose G is a locally finite infinite graph. Then G has a colorization.

Proof Note that without loss of generality we can assume that G is connected. Let v G be a vertex in G. Consider all the paths s E(G) of length m N from v to other vertices in G. The union of these paths is a finite connected subgraph Gm G. By theorem(2.21), there exists a colorization clm Cl(Gm). Next Cl(Gm) can be considered as a subset of with integer entries. Let us pick randomly one of these graphs say . Thus there exist an infinite subsequence (m ≤ mi)i of (N), and a colorization cl1, Cl(G1) such that for each Gmi the restriction of clmi to G1 will agree with cl1,∞. Proceeding inductively we can construct an increasing sequence of finite subgraphs of G, G1 G2 …… Gk …, where for each ≤ k, Gk has a colorization clk,∞, with the property that the restriction of clk+1,∞ to Gk will be equal to clk,∞. But G =S(Gk)k, and this complete the proof.

3. Appendix

In this section we are going to proof some technical lemmas needed in the proof of number of the lemmas and theorems in the above

Theorem 3.22 Keeping the same notations as in the above. let S G be a max closed curve. Then S EBound(G).

Proof As we demostrated, if (Si), i = 1,2, … m be the set of all max closed curves, then G is the union of the sets SiCG together with the paths si,j, i,j = 1, 2, …, m, where si,j is the unique path connecting Si to Sj. By the finiteness of the Graph G we can assume that each of the max closed curves is a circle and the connecting paths are straight lines going through the centers of corresponding circles. Next for each of the circles Si there exists a circle Si,l with the same center but strictly larger than Si. By taking Si,l close enough to Si we can make sure that Si,l does not intersect any other max closed curves or the paths connecting them to any other max closed curve other than Si. set bi,j be the intersection of si,j with Si,l. Now moving clockwise on Si,l, consider two points bi,j,1 < bi,j < bi,j,2 on Si,l. We can choose them close enough so that if we draw lines si,j,1 and si,j,2, parallel to si,j intersecting Sj,l at bi,j,2 and bi,j,1 respectively, with bj,i,2 > bj,i,1, then si,j,k, k = 1, 2 intersect G at Si and Sj only. Next let aj,i,k, k = 1, 2, be the intersection of si,j,k, k = 1, 2 with Sj respectively. let us define the closed curve Si,j,s to be de_ned to be the union of [ai,j,1, aj,i,2] si,j,1, [aj,i,2, aj,i,1] Sj, [aj,i,1, ai,j,2] si,j,2 and [ai,j,2, ai,j,1] Si. Then it is clear that Si,j,s contains si,j in its interior. At this point we assume that Si is connected to the sequence of max closed curves (Sj), j = 2, …, m1, where each of the above closed curves is connected to Si only. Next for each integer 2 ≤ j ≤ m we define a loop Ω(i,j) (G)c to be a path which is the union of following paths, and Now suppose Sj is connected to more than one closed curve Ordering the points of intersection of sj,k with Sj. Let aj,k, be the sequence of the above vertices. At this point we assume that The sequence of closed curves that are connected to Sj, j = 1,2, …, m1 are not connected to any other max closed curve. Next for a fixed 2 ≤ j1 ≤ m1 and we defined the loop to be a path going from to and back to . Now we want to extend the definition of loop to more complicated case. we want to define a path Ω(i,j1)Gc, going from to and back to Si,l. Set to be equal to the union of the following paths, and Using our assumptions each one of the paths , is well defined hence the above formula is going to identify the path We call the above formula the loop formula. We saw that the loop formula is valid for two special cases. We want to show that the loop formula will identify the path from to and back to in the most general case. By the loop formula we can identify , if we can identify for all the max closed curves connected to except Si. Similarly to identify Ω(j1, k), it is enough to identify all the loops Ω(j2, k) where ≠ Si is one of the max closed curves that are connected to , furthermore for each 2 ≤ k, Sk is one of the max closed curves that is connected to . We call this the stage (j1, j2) of calculation. inductively we have stages (j1, j2, …, jn) of calculation. If there exists some integer n0 such that for n ≥ n0 at every stage (j1, j2, …, jn) we can calculate (jn, k) for all max closed curves that are connected to and that are different from , then we are done. But because of the finiteness of G, there exists an integer n0 such that for n ≥ n0, Sjn is only connected to . This implies that at the stages (j1, j2, …, ) we can calculate (,k), so by induction we are done. This implies the following lemma

Lemma 3.22.1 Keeping the same notations as in the above. For every connected max closed curves Si and Sj there exists a path Ω(i, j) Gc going from Si,l to Sj,l and back to Si,1.

To complete the proof of the theorem we have to show that for any point x G, and v D(G)c, there exists a path s Gc connecting x to v. Next We need to employ some new notation. As we mentioned we say two max closed curves S1 G and S2 G are connected, if they are connected by the path s1,2. By chain of max closed curves we mean a sequence (Si), i = 1, 2, …, m such that for each i ≤ m, Si and Si+1 are connected. Now without loss of generality we can assume S1 x = for some max closed curve S1 G, where , is a closed curves connected to S1. The other cases can be overcome using some minor technicalities. Now there exists a path s1 (S1)c from to , furthermore by the structure of G we can assume that in fact s1 Gc. Also there is a path from to v. Moving from v to on s2 suppose the first point that we intersect G is y = ak,k+1 Sk, Where Sk, Sk+1 G are connected max closed curves. The other cases can be overcome with minor technicality. At this point without loss of generality we can assume that s2 will intersects Sk,1 first time at . But by the structure of G, the exists a chain of closed curves rom to . Next let us define the path , by In this paths all the intervals are on S1,l and it takes point to point . Note since we number the max closed curves connected to S1 by moving clockwise on by our definition, . Let us denote by (It is also clear that if none of the points in the interval were connected to another max closed curve then Now for an integer i ≤ k, consider the path s(i,i + 2) , that is theunion of and Finally consider the paths , and . At this end the path is a path in Gc taking x to v and this complete the proof of the theorem.

References

[1]  Allaire, F, “Another proof of the four colour theoremPart I”, Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer. 20: 372. (1997).
In article      
 
[2]  Appel, Kenneth; Haken, Wolfgang, “Every Planar Map is Four Colorable Part I. Discharging”, Illinois Journal of Mathematics 21: 429490. (1977).
In article      
 
[3]  Appel, Kenneth; Haken, Wolfgang; Koch, John, “Every Planar Map is Four Colorable Part II. Reducibility”, Illinois Journal of Mathematics 21: 491567. (1977).
In article      
 
[4]  Appel, Kenneth; Haken, Wolfgang, “Solution of the Four Color Map Problem”, Scienti_c American 237 (4): 108121, (October 1977).
In article      
 
[5]  Appel, Kenneth; Haken,Wolfgang, Every Planar Map is Four-Colorable, Providence, RI: American Mathematical Society. (1989).
In article      View Article
 
[6]  Bernhart, Frank R, “A digest of the four color theorem.”, Journal of Graph Theory 1: 207225, (1977).
In article      View Article
 
[7]  Borodin, O. V, “Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs”, Metody Diskretnogo Analiza (41): 1226, 108, MR 832128. (1984).
In article      
 
[8]  Cayley, Arthur, “On the colourings of maps”, Proc. Royal Geographical Society (Blackwell Publishing) 1 (4): 259261, (1879).
In article      View Article
 
[9]  Fritsch, Rudolf; Fritsch, Gerda, The Four Color Theorem: History, Topological Foundations and Idea of Proof, New York: Springer, (1998).
In article      View Article
 
[10]  Gonthier, Georges, “Formal ProofThe Four-Color Theorem”, Notices of the American Mathematical Society 55 (11): 13821393, (2008).
In article      
 
[11]  Gonthier, Georges, A computer-checked proof of the four colour theorem, unpublished
In article      
 
[12]  (2005) Hadwiger, Hugo, “ber eine Klassi_kation der Streckenkom-plexe”, Vierteljschr. Naturforsch. Ges. Zrich 88: 133143. (1943).
In article      
 
[13]  Hale, Thomas C, The Jordan Curve Theorem formaly and informaly, The American Monthly 114(10):889-894.
In article      
 
[14]  Wilson, Richard and Newmann Victort Lara, Digital Jordan curves, Topology and its applications, Volume 46, Issued 3, 30 October (1992).
In article      
 
[15]  Tymchatyn,Ed,(Department of mathematics University of Saskatchewan), exchange of ideas and communications. (2014).
In article      
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn