From Puzzles to Programming

Recursive Planar graphs are Four Colorable

Fadi Jabr, MD

Abstract: The four color theorem states that every loopless planar graph admits a vertex coloring with at most four different colors. The only available and acceptable proof of this theorem depends on computer. Here, I discuss a new type of planar graphs built by recursion and prove that they are four colorable.

1. Introduction

A graph G (V, E, I) consists of a finite set of vertices V{v₁, v₂, v₃,……,v_n}, a finite set of edges E{e₁, e₂, e₃,……, e_m}, and an incidence relation I between them. Each edge is incident with two vertices called its ends. An edge whose ends are equal is called a loop. The incidence function I is written as

I = { V(e)|e Î E } in which each edge e has an endpoint set V(e) containing either one or two elements of the vertex set V. Two vertices v and u are called adjacent if they are the endpoints of an edge e. In this case, e is incident to v and u, and the incidence function can be written as I (e) = [u, v] or simply uv.

A planar graph is a graph that can be embedded (drawn) in a plane i.e. without crossing of its edges. A simple planar graph is loopless and has no multiple edges. In this paper only simple planar graphs will be discussed and thus they will be referred to as planar graphs and will be denoted by G.

A face or region in a planar graph G is defined as a set of all points X in plane disjoint from G i.e. not belonging to an edge and are not vertices of G where any two points x, and y in X can be joined by a Jordan curve all whose points on the plane are disjoint from G. The boundaries of faces are edges and vertices. The “unbounded” face is called the infinite face. The set of resultant faces will be denoted by F.

Let |V|, |E|, and |F| denote respectively the number of vertices, edges and faces of G, then Euler equation states that |V| - |E| + |F| = 2. For simplicity, the notations V, E, and F will be used respectively instead of |V|, |E|, and |F| in algebraic equations i.e. V-E+F=2.

2. Maximal Planar graph

Definition: A maximal planar graph is a planar graph to which no new edges can be added without violating planarity.

Lemma 1 and Theorem 1 are due to Saaty and Kainen [1].

Lemma 1: If G is a planar graph in which some region R has on its boundary four or more vertices, some pairs of these vertices cannot be adjacent.

Proof: If all pairs of vertices of R are adjacent with edges drawn exterior to R, we can add a vertex in the interior of R and join it (without edge crossings) to each vertex of R without violating planarity. But, the result for the vertices of R plus the new vertex is a complete graph on five or more vertices which is known to be non-planar. Hence, some pair of vertices on the boundary of R cannot be adjacent [1].

Theorem 1: Let G be a planar graph. G is maximal if and only if every region including the unbounded region (the infinite face) has three sides.

Proof: Let G be a maximal planar graph and assume that some region R of G has four or more vertices on its boundary. By lemma 1, some pair of these vertices is not adjacent. We can join them by an edge and the resulting graph is still planar. This contradicts the fact that G was a maximal planar.

The converse is true. If every Region of G is bounded by 3 sides i.e. 3F = 2E and E = 3V – 6 (substituting F for 2E/3 in Euler’s equation), then G must be maximal planar graph, i.e. we can not add any more edges to it since it has the maximum number of edges a planar graph can have [1].

Definitions

From theorem 1 planar graph is called a triangulation where every face is bound by 3 sides.

A vertex v_ex is called an exterior vertex in G if it can be joined to any point in the infinite face without crossing an edge in G.

A vertex v_in is called an interior vertex of G if it cannot be joined to any point in the infinite face without crossing at least one or more edges in G.

Edges bounding the infinite face are called exterior edges.

Corollary 1: Every maximal planar graph will have only 3 exterior vertices and only 3 exterior sides or edges.

Proof: Suppose to the contrary, G has four or more exterior vertices then any pair of these vertices can be joined (become adjacent) by an edge drawn in the infinite face (exterior to the graph). But this contradicts the fact that G was a maximal planar graph. G must have 3 or less exterior vertices. If G has less than 3 exterior vertices then the unbounded face has 2 or 1 sides (double edges or a loop) a contradiction to theorem 1 and also to the definition of simple planar graph. Therefore, G must have only three exterior vertices. Consequently, G has only 3 exterior edges each connecting a pair of these exterior edges.

Definitions:

A maximal circuit of a graph is the circuit that surrounds the whole graph with all of its faces. According to corollary 1, the maximal circuit in a maximal planar graph is a 3-cyclic arc since it is formed by three exterior vertices and passes each of the three exterior edges only once. It is denoted by C_n (u, v, w) of G_n or simply C_n where n is the number of vertices in graph G_n, and u, v, and w are the exterior vertices of the graph.

A spanning planar subgraph G’ of G (V, E, I) is a planar graph G’ (V’, E’, I) where V = V’, and E’ is a subset of E.

A maximal planar graph can be obtained from a subgraph by adding all remaining edges in E and not in E’ (E|E’) without violating planarity. 

Deleting loops and parallel edges and then adding new edges in a planar graph G to obtain a maximal planar graph is called a standardization of G.

The four color theorem (FCT) asserts that every planar graph G can be four colored i.e. a mapping L: V(G) → {b, g, r, y} such that L(v) ≠ L(u) for every edge of G with ends v and u. The conjecture dates back to F. Guthrie in 1852. Attempted proof was done by Kempe who introduced the Kempe chain argument. The conjecture remained open until proof was found by Appel and Haken in 1976 and later on modified by Robertson, Sanders, Seymour, and Thomas in 1996 [2, 3]. However, both proofs needed computers for check up though to a lesser extent in the later.

The basic idea in the last proof is to exhibit a set of “configurations” [they are 633 configurations] or graphs and then prove that none of them can appear in a minimal counterexample to the FCT, because if one appeared then it can be “reduced” and replaced by something smaller, to make a smaller counterexample of the FCT. In the second part, they proved that at least one of the 633 configurations appeared in every internally 6-connected triangulation (this is called unavoidability). Consequently, there is no minimal counterexample, and so the FCT is true. Both reducibility and unavoidability required hand checking or computer checking [2, 3].

In this paper, the idea is to prove that certain maximal planar graphs called recursive or hierarchical are four colored without the need for “configurations”, “reducibility” and “unavoidability”. Rather, any hierarchical maximal planar graph can be built up by recursively adding vertices to a “nidus” (the smallest maximal planar graph) and as it is being built up, it will be shown that it can be easily four colored. Before proceeding to the proof, let us introduce recursive planar graphs.

3. Recursive Planar Graphs

Let V_n be a set of vertices {v₁, v₂, v₃,……,v_n}, then the set of recursive planar graphs G_n are planar graphs each having V_n vertices and are built as follows: First, take any 3 vertices u, v, and w in V_n and join them. The edges uv, vw and wu will form a maximal circuit C₃ and the resultant graph G₃ is the smallest planar graph called unit or nidus (figure 1). All these three vertices are exterior and all can become adjacent to a fourth vertex y from V_n. Now, as y joins vertices on C₃, one of the edges yu, yv, or yw and one of the vertices v, u, or w will become interior to preserve planarity in G₄. Then C₄ will have only 3 exterior vertices and it will be formed by set of vertices (y, u, v), (y, u, w), or (y, v, w). The number of G₄ planar graphs formed in this way is three though they are isomorphic to each other (figure 2). To make G₅ planar graphs, we join a 5^th vertex from V_n to the 3 vertices in C₄ of each of the three G₄ graphs (figure 3). The number of G₅ graphs formed is 3² = 9 isomorphic graphs. We continue in the same way until we reach G_n-1 graphs. We join the nth vertex v_n to three vertices in C_n-1 of each of the G_n-1 graphs to get G_n planar graphs. The G_n planar graphs generated using n vertices of V_n in this recursive way are called the recursive planar graphs of V_n. It is easy to notice that their number is at least 3^(n-3) graphs of which many are isomorphic to each other.

Figure1. Nidus or unit (the smallest maximal planar graph) is formed by 3 vertices.

Figure 2. Three G₄ recursive and isomorphic planar graphs formed by joining v₄ to the three nidus vertices.

Figure 3. Three G₅ recursive planar graphs formed by joining v₅ to the vertices (v₁, v₃, v₄) of the maximal circuit of one of the G₄ recursive planar graphs in figure 2. Note that they are isomorphic.

Recursion on planar graphs:

A recursive planar graph G_n = R (G_n-1) = v + G_n-1 is obtained by the union (+) of v and C_n-1 where union means joining v to vertices of C_n-1. We say G_n is generated by recursion on G_n-1.

We can write G_n = R (R (G_n-2)) = R² (G_n-2). In general, G_n = R^n-3 (G₃).

Theorem 2: All recursive planar graphs are maximal planar graphs.

Proof: The proof proceeds by induction as follows.

First, the smallest recursive planar graph G₃ (U₃, E₃, I) is a maximal planar graph because according to theorem 1 each of its two regions (one is the infinite region) is bound by 3 sides.

Now, suppose that all G_n (U_n, E_n, I) recursive planar graphs are maximal planar graphs. We need to prove that all G_n+1 recursive planar graphs are also maximal planar graphs. Let C_n be the maximal circuit of one of these G_n graphs. According to definition of recursion as well as to theorem 1, C_n should have only 3 exterior vertices. Let u be the (n+1)^th vertex in the infinite face and disjoint from G_n. Now, join u to the vertices of C_n to form G_n+1 planar graphs. Three edges and two faces thus will be added to G. Each of these two new faces is bound by 3 sides. Since G_n is a maximal planar graph, each of its faces is also bound by 3 sides. Therefore, every face in G_n+1 is bound by three sides.

Conversely, we can say that since G_n is a maximal planar graph, then every one of its regions is bound by 3 sides i.e. E_n = 3n – 6 = maximum number of edges in G_n. Now, E_n+1 = E_n + 3 = 3n – 6 + 3 = 3(n+1) – 6 = maximum number of edges in G_n+1. It follows that G_n+1 is a maximal planar graph. Therefore, every recursive planar graph is a maximal planar graph.

Theorem 3: Every recursive planar graph is four colorable.

Proof: Again, induction method will be used.

G₄ is the smallest recursive planar graph that is clearly four colorable. Every one of the three exterior vertices as well as the interior vertex is mapped to one color in set {b, g, r, y}.

Assume G_n is a four colorable recursive planar graph. We need to prove that G_n+1 recursive planar graphs are also four colorable. Let C_n formed by the three adjacent exterior vertices (x, y, z) be the maximal circuit of G_n. Since G_n is four colorable then each of the vertices x, y and z is mapped to a different color i.e. L(x) ≠ L(y) ≠ L(z). Let u be the (n+1)^th vertex in the infinite face and disjoint from G_n. Now, join u to x, y, and z to form G_n+1 recursive planar graphs. Obviously, u can be mapped to the remaining 4^th color without violating the four color conjecture. Hence, G_n+1 are four colorable. Therefore, by induction every recursive planar graph is four colorable. See figure 4 as an example for coloring a G₅ recursive planar graph.

Figure 4: Coloring scheme of one of G₅ = (v₅ + G₄) recursive planar graphs. The vertex labeled 2 is an interior vertex (inside C₄) and thus vertex 5 can be mapped to the same color (yellow) as that of vertex 2. Note that in G₅, vertex 4 becomes interior, but topologically either vertices 1 or 3 can become interior and vertex 4 will be exterior.

Definitions

The degree of a vertex v denoted by d (v) is the number of edges whose ends are at vertex v.

The sum degree of a graph G = D (G) is the sum of degrees of its vertices. Obviously, D (G) = 2 E where E is the number of edges in G.

A graph G is regular if all the degrees of its vertices are the same i.e. d (v) = k for every v in G and we call G k-regular.

Theorem 4: The number of maximal planar graphs that are k-regular is finite.

Proof: Let G (V, E, I) be a maximal planar graph. Then E = (3V – 6).

D (G) = 2 E = 2(3V-6) = 6V-12.

 Since G is k-regular then all vertices v of G will have the same degree d (v) = k. Hence, d (v) = k = D/V = 6 – 12/V, or (6V – 12) ≡ 0 (mod V). Since k is a positive integer, then the only values for V and k that satisfy the equation V = 12 / (6 – k) are V = 3, 6, and 12 corresponding to k = 2, 4, and 5 respectively. In other word, only G₃, G₆, and G₁₂ maximal planar graphs can be regular having k = 2, 4, and 5 respectively.

Theorem 5: For a set of n vertices, the recursive planar graphs G_n are not necessary all the maximal planar graphs of n vertices.

Proof: To proceed in this proof is simply to find at least one maximal planar graph G of n vertices that does not belong to the recursive planar graphs G_n for any n more than three.  The 4-regular G₆ maximal planar graph is an example. During recursion on G₃, one of the vertices let say u will become interior with a degree of three. Since u is not accessible to joining any exterior vertex during recursion on G₄, followed by recursion on G₅, its degree d (u) will remain three in G₆. Thus, recursive maximal planar graphs G₆ cannot be 4-regular. Hence, not all maximal planar graphs can be generated by recursion alone.

4. Discussion

This paper presents a new idea of recursion on graphs and a proof that they are four colorable. I believe that these types of graphs will be useful addition to the graph theory as well as the field of combinatorics and computer science. Though recursive planar graphs represent a portion of maximal planar graphs, they might be very useful in developing a new proof for the four color theorem that does not rely on computers.

5. References

1. T. L. Saaty and P. C. Kainen, The Four –Color Problem Assault and Conquest, Dover Publications, New York, 1986.
2. K. Appel and W. Haken, Every planar map is four colorable, A. M. S. Contemporary Math. 98 (1989). MR 91m:05079
3. N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas. A new proof of the four-color theorem. Electronic Research Announcements of the American Mathematical Society. Volume 2 (1); August 1996: 17-25.

Exhibition Function in Recursive Planar Graphs

During recursion on G_j-1 and to preserve planarity of G_j, one vertex say u on C_j-1 must become an interior vertex (inside C_j) and not accessible to join additional vertices in the infinite face. In order to become adjacent to an additional vertex v during subsequent recursion on G_j, vertex u has to convert to an exterior vertex again. Let us call this conversion function of an interior vertex to an exterior vertex as an “exhibition”. Denote this exhibition of vertex u and joining u to v by € (G_j).

As an example, in figure 5, vertex 2 becomes interior inside C₄ (1, 3, and 4) and thus is not accessible to join vertex 5. The exhibition function € (G₄) aim is to join vertices 2 and 5. To do so, first we have to delete any of the 3 edges [1, 3], [3, 4] or [4, 1] in C₄ and second to draw edge [2, 5] (figure 6). Using recursion along with exhibition function, it is easy to make maximal planar graphs not generated by recursion alone such as 6-regular graphs and other planar graphs (figure 7). In figure 8, one of the G₉ planar graphs called the Fritsch graph is made using recursion and exhibition functions.

Figure 5: G₅ with highlighting of C₄ (1,  3,  4). Vertex 2 is clearly interior inside C₄ and cannot be adjacent to vertex 5.

Figure 6: Some G₅ graphs formed by recursion on G₄ = R (G₄) and exhibition of vertex 2, € (G₄) done by deletion any of the 3 edges [1, 3], [3, 4] or [4, 1] in C₄ and then drawing edge [2, 5].

Figure 7: A 4-regular G₆ recursive planar graph is made with recursion on G₅, and exhibition function € (G₅), exposing vertex 2 by deleting [1, 3] followed by joining vertices 2 and 6.

Figure 8: Construction of one of G₉ planar graphs (Fritsch graph) using both recursion and exhibition functions. The set of numbers represent the set of degrees of vertices at each level of recursion with or without exhibition. For example the set (5, 5, 5, 5, 5, 5, 4, 4, 4) means that there are six vertices of degree 5, and there are three vertices of degree 4.

Definition: Let G_n+1 = R (G_n) to be the recursion graph on G_n by union of C_n and vertex v. Let u be an interior vertex inside C_n (x, y, z) where u is adjacent to at least one of the vertices pair {p, q} where {p, q} belongs to {{x, y}, {x, z}, {y, z}}.  We define exhibition function € (G_n) = G_n – [p, q] + [u, v].

Theorem 6: The graph G_n+1 obtained by recursion on a maximal planar graph G_n, R (G_n) and exhibition function € (G_n) is a maximal planar graph.

Proof: We showed in theorem 2 that R (G_n) is a maximal planar graph. In exhibition operation € (G_n), one edge pq is deleted and another uv added. The 2 triangular faces [pqu] and [pqv] are replaced by two triangular faces [puv] and [quv]. Hence, every region remains triangular having 3 vertices and 3 edges. Therefore, G_n+1 is a maximal planar graph.

Theorem 7: Every graph G_n+1 obtained by recursion on a maximal planar graph G_n, R (G_n) and exhibition function € (G_n) is a four colorable.

Proof: In theorem 3, it was shown that R (G_n) is four colorable. Then each of the vertices x, y, and z of C_n is mapped to a different color in {blue, green, red, yellow} i.e. L (x) ≠ L (y) ≠ L (z). Clearly, without the exhibition, vertex v will be mapped to the remaining fourth color. Upon application of exhibition, however, vertex v will join an interior vertex u, of course, after deletion of one of the edges [x, y], [x, z], or [y, z]. Suppose that [x, y] is the edge to be deleted. In this case, u is adjacent to both x and y and not necessarily z. There are two possibilities for coloring v. In the first one, if u and z are not adjacent or they are mapped to the same color i.e. L (u) = L (z) then v can be mapped to the remaining fourth color while x and y retain their colors. In the second possibility, similar to the famous Kempe chain argument, L (u) ≠ L (z) then map x and y to the same color as follows: If x is adjacent to any other vertex with the same color as of y then change the color of y to that of x else change the color of x to that of y. Therefore, the graph G_n+1 obtained by R (G_n) and exhibition € (G_n) is four colorable. See figure 9.

Figure 9: On the upper left, recursive planar graph G₅ is shown. On the upper right, G₆ is generated by adding vertex 6 to C₅ (1, 3, 5). Vertex 6 is mapped to a blue color different from the colors of the vertices in C₅. In the lower right, exhibition function on vertex 2 was applied along with recursion on G₅. Because vertex 2 has same color (yellow) as that of one of the vertices in C₅ (vertex 5), then vertex 6 will still be colored blue and vertices 1 and 3 retain their colors. In the lower left, the exposed vertex 4 has blue color different from those vertices in C₅. Therefore, the disconnected vertices 1 (red) and 5 (yellow) have to had the same color. Now, since vertex 1 is adjacent to vertex 2 colored yellow, then vertex 5 will be mapped to red as vertex 1, leaving its previous yellow color for vertex 6.

Maximal planarity limitations on the exhibition function:

The purpose of € is to generate planar graphs G_n+1 not generated by recursion alone. Unlike recursion whose limitation is only to join the additional vertex v just to the maximal circuit, the function € has several limitations. First, it is not allowed to delete more than one edge of the maximal circuit to join v to an interior vertex using multiple edges because maximal planarity will be lost. In a similar way, v cannot join an interior vertex u inside C_j (where j < or = to n - 1) unless u is adjacent to at least a pair of vertices of C_j or in other words, C_j has a common edge with C_n. Otherwise, in joining u and v, more than one edge have to be deleted and again the maximal planarity of G_n+1 will be lost.

Color limitations on the exhibition function:

First, it is not allowed to join v to multiple interior vertices during one recursion. The reason is that v has to join at least five vertices instead of just four or three vertices and thus very likely v has to be a colored by a fifth color. Because of this color limitation, this method will always generate maximal planar graphs of hereditary minimum degree 4. That is there is always a vertex of degree 4, and when it is deleted, the remaining graph still has a vertex of degree 4, etc…. I tried to use this method involving only the two functions recursion and exhibition to generate graphs with minimum degree 5, but unfortunately, it did not work. One of the smallest such graphs is the graph of the regular icosahedrons below:

Figure 10. An icosahedron of 12 vertices each of degree 5 (a planar graph with minimum degree 5) is a G₁₂ (5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5) maximal regular planar graph of k = 5 (see theorem 4). Such graph and other planar graphs with minimum degree 5 cannot be generated by functions recursion and exhibition alone.

Generation of an icosahedron:

However, it is easy to show that such an icosahedron graph can be generated from a Fritsch graph G9 (5, 5, 5, 5, 5, 4, 4, 4) which we mentioned earlier in figure 8 (see below).

We already proved that a 4 colorable Fritsch graph can be generated using the method of recursion and exhibition. So it remains to form a 4 colorable icosahedron from a four colorable Fritsch graph. One way to do so is as follows: Since G9 (figure I below) has 3 exterior vertices each of different color; we can attach 3 additional vertices simultaneously using exhibition in such a way that each of the 3 added vertices joins 2 exterior vertices and one interior vertex and thus have the remaining fourth color. What we get is a graph in figure II below (5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 3, 3). It turns out, that these 3 added vertices will have different colors. Now, join these 3 added vertices together to get a 4 colorable icosahedron (figure III).

The problem is that there are plenty of planar graphs with minimum degree 5. The latest proof of the four color theory by Robertson et al [7] still uses 633 cases. To generate them with the two functions recursion and exhibition is not feasible. Using other modifications, such as we did to generate the icosahedrons graphs, will be enormously complicated.

Another subtle phenomenon is called “saturation” of interior vertex. It means that applying exhibition on an interior vertex in two successive recursions may not allow four coloring.

This last restriction needs not to be encountered in building any maximal planar graph with hereditary minimum degree 4.

Exhibition function without the color limitations is called “unrestricted” exhibition or just exhibition. It is “restricted” when applying the color limitations.

Conjecture 1: Any finite maximal planar graph G_n (n > 3) with hereditary minimum degree 4 can be generated by the use of n-3 recursions and 0 up to n-3 exhibitions.

This can be easily proved by induction.

A stronger conjecture is as follows:

Conjecture 2: Any finite maximal planar graph G_n of hereditary minimum degree 4 can be generated by the use of n-3 recursions and 0 up to n-3 restricted exhibitions.

Corollary: Any planar graph with hereditary minimum degree 4 is four colorable. This follows from conjecture 2 since recursion and restricted exhibition generated graphs that are four colorable.

Summary

The famous and well known proof of the four color theory resides mainly on finding reducible configurations in any planar graph. In the above manuscript, we propose an idea of building any maximal planar graph with hereditary minimum degree of 4 using recursion and exhibition. During this building process, the graph is four colored at the same time it is being built. I would approximate it to like building from scratch any brick wall having different configurations adding one brick at a time using only four colors for each instead of searching for certain configurations on that wall and proving that they are four colorable. However, this method of recursion and exhibition failed to generate maximal planar graphs with minimum degree of 5. One example is the icosahedron. Certain modifications were required to generate such graph using recursion and exhibition alone. Unfortunately, the list of maximal planar graphs with minimum degree of 5 is large, reduced recently to 633 cases, and modifying the recursion and exhibition to generate all of them will be enormously complicated and I guess a computer is still needed to do so.