| In a maximal planar graph all regions are triangular. If a vertex is added to an existing face and connected to the surrounding vertices, the new vertex has a valence of 3. |  |
ABSTRACT This paper presents a new method for generating maximal planar graphs inductively. The presented method overcomes the counterexample provided for past failed methods and demonstrates the new method provable. Ways are suggested that the method may be used in attacking the 4-color problem.
Inductive arguments to prove the 4 color theorem have failed in the past because no method was found for generating all maximal planar graphs inductively.1 Previous attempts have tried to increase the size of a maximal graph by adding a vertex to either a face or to an existing edge. 2 It can be shown that that approach fails. 3 Dave Witte showed me a counter-example to the traditional argument. That counter-example is the skeleton of the icosahedron.
| In a maximal planar graph all regions are triangular. If a vertex is added to an existing face and connected to the surrounding vertices, the new vertex has a valence of 3. | |
If a vertex, E, is added to an existing edge, AB, that vertex will have a valence of either 3 or 4, depending upon how the additional edges are connected. Reconnecting AB leaves the new vertex, E, with a valence of 3, yielding the same result as adding a vertex to face ABC. Connecting the new vertex, E, to both C and D leaves the added vertex with a valence of 4. By symmetry between C and D there is no other way to connect vertices. Either process always leaves the last vertex added having a valence of either 3 or 4. Consequently, any graph constructed by this process, starting with a simple triangle, must always have a vertex with a valence of 3 or 4, the valence of the last vertex added.
 |
 |
 |
As we saw, adding a vertex to a face or
to an edge always leaves a vertex with a valence of 3 or 4, consequently,
a graph with all vertices having a valence of 5 or more cannot be constructed by
such an inductive process. The simplest example of such a graph - one that
cannot be constructed by this process of adding a vertex to a face or to an edge
-- is the skeleton of the icosahedron; it has 12 vertices each with valence 5.
What's wrong with adding a vertex to either a face or an edge? Why can't these generate all maximal graphs? It turns out that there is a third possibility, one which is usually dismissed as trivial. One can add a vertex to an existing vertex. But that, it is argued, just makes coincident points and does not increase the size of the graph. (It may also be noted that one of the ways of adding edges to a graph with a vertex added to an existing edge produces the same result as adding a vertex to a face.)
The way we have looked at increasing the size of a maximal planar graph seems most unaesthetic; it contains redundancies and trivialities and is incomplete. (It can't generate all maximal graphs.) I found a better way of looking at the process, and that way generates all the other ways as special cases. It overcomes the icosahedron problem. Moreover, it can be correctly argued that it successfully generates all maximal planar graphs inductively.
In the new way of generating maximal planar graphs inductively there is only one way for increasing the size of a maximal planar graph of size N; but there are three sub-cases. One sub-case is equivalent to adding a vertex to a face, and one sub-case is equivalent to the one way of adding edges after adding a vertex to an edge that yields a vertex of valence four, but the third sub-case has no equivalent. It is this third sub-case that overcomes the problem of generating the icosahedron skeleton.
To generate a maximal graph of size N+1 from a maximal graph of size N, I add a vertex to an existing vertex and then draw the two vertices apart and into a new edge. In the process two existing edges are divided into two pair of edges; one of each pair is connected to the opposite ends of the newly created edge (two edges are drawn into two triangles). It is immediately apparent that any maximal planar graph of size N+1 can be collapsed along any edge into a maximal planar graph of size N. The process is completely reversible, so there are no maximal planar graphs of size N+1 that cannot be generated by this process from some maximal planar graph of size N. The proof is trivial.
The three sub-cases. Essentially, the edges entering a vertex are divided up between the two new vertices formed. In each case a pair of these edges is duplicated, and a new edge is created between the old an new vertex. The differences among the three sub-cases depend upon how many of the existing edges go with the new point.
Case 1. The new vertex may be drawn
(pulled) from the old in a direction that divides two adjacent edges into pairs
of new edges. (Two edges go with the new point.) This is
equivalent to adding a vertex to the face between these edges. This is
possible with any vertex that has a valence of 2 or more. In this case the
graph is increased in size by 1 vertex and 3 edges. The new vertex has a
valence of 3. The valence of each of two adjacent vertices is
increased by 1, and the valance of the old vertex is increased by 1. The
total valence increase is 6.
Case 2. The new vertex may be drawn from the old in a direction that divides
non-adjacent edges with only one intermediate edge into pairs of new edges. This
is the same as drawing the vertex along an existing edge while edges adjacent to
that edge divide into two new edges. This is equivalent to adding a vertex to
that edge and 
connecting the new vertex to
the apices of the triangles adjacent to the edge prior to adding the vertex. For
this to happen the vertex being split must have a valence of at least 4,
otherwise the split would be into the face opposite the edge, as those edges
would not have one between. In this case the graph is increased in size by 1
vertex and 3 edges, and the new vertex has a valence of 4. The valence of each
of the two adjacent vertices is increased by 1, and the valance of the old
vertex is unchanged. The total valence increase is 6.
Case 3. The new vertex may be drawn from the old in a direction that divides
in two non-adjacent edges with at least two intermediate edges. For this to
happen the vertex being split must have a valence of at least 6; 
otherwise
the split would be into the region opposite the face and those edges would not
have two edges between them. In the case that the number of intervening
edges is exactly 2, the graph is increased in size by 1 vertex and 3 edges, and
the new vertex has a valence of 5. The valence of each of the two adjacent
vertices is increased by 1, and the valance of the old vertex is decreased by 1.
The total valence increase is 6.
In the case where the number of intervening edges is more than 2, the graph is increased in size by 1 vertex and 3 edges, and the new vertex has a valence of 3 plus the number of intervening edges (3+K). The valence of each of the two adjacent vertices is increased by 1 (2), and the valance of the old vertex is decreased by the number of intervening edges less 1 (V-(K-1)). [K edges are take away and one is added.] The total valence increase is 6 (3+K +2 +V-K+1 -V). But we also know that both vertices so formed have a valence of 5 or greater because the new vertex, with its added edge, has a valence of K+2+1 where K >= 2, and, by symmetry, so does the old vertex.
One simple mechanism, with no omissions, and without redundancies, generates the next larger sized maximal planar graph. This is most aesthetic. An added benefit is that this mechanism can generate maximal planar graphs from a single point! Divide a point into an edge; divide one end into an edge -- creating a simple triangle; divide a vertex of a simple triangle to produce M4, etc. The process is capable of generating all maximal planar graphs inductively, starting with a single point!.
Using this development toward solving the 4 color problem, however, is another matter. The inductive approach assumes that a maximal graph of size N (or less) is colorable; it then shows that any means of generating a maximal planar graph of size N+1 from one of size N (or less) produces one that is still colorable. Case 1 is trivial. Case 2 avails itself of the merge and split technique, and is straight forward. Case 3, on the other hand, is not so straight forward.
Suppose we have a graph G of size N and a vertex, V, of degree K (>= 6), and we split that vertex into two vertices (V' and V"), using case 3 as our model. One of the things we know is that vertex V existed in a K-circuit, so vertices V' and V" form a non-trivial subgraph enclosed in a circuit of length K. We also know that this K-circuit is at most 3-colored -- V having the fourth color. But because the degree of both V' and V" are at least 5, such arguments as worked for sub-cases 1 and 2 will not work. In order for V' and V" to have different colors, the dividing point of the K-circuit, the ends of the edges that were split, must divide the K circuit in such a way that any new 3-coloring of each division differs in the third color. (One or both sides could be 2-colored.) In order to show the inductive inference on the third case we must show the following. Removing vertex V from graph G must permit the K-circuit, which was 3-colored, to be colored as two 3-color chains joined at both ends, but such that each chain is missing the third color of the other chain.
Once, however, I got to this point, I could see that this third sub-case opens the whole Pandora's box of prior problems with the four color problem. Solving the implication from N (or <N) to N+1 (N) for maximal graphs for the third sub-case is not such a simple matter as solving it for the first two cases -- the simplicity of which has misled many a novice, myself included, into thinking a solution was at hand. Perhaps this new way of looking at inductively increasing the size of maximal planar graphs will be something some more seasoned experts can make use of. I would like to see an elegant logical argument which can be followed as easily as Locke suggested and I herby offer this approach to the induction part of the problem into the graph community for anyone to try to use.
1. Thomas L. Saaty and Paul C. Kainen, The Four Color Problem: Assaults and Conquest, (1977), Dover edition, Dover Publications, New York, 1986, p. 60.
2. William Dilworth, An Inductive Theorem for Maximal Planar Graphs, dated June 17, 1992, submitted to Illinois Journal of Mathematics, and accepted for review as of July 27, 1992.
3. Ralph E. Kenyon Jr., A review of An Inductive Theorem for Maximal Planar Graphs, submitted to Illinois Journal of Mathematics, November 25, 1992.
| This page was updated by Ralph Kenyon on 2009/11/16 at 21:21 and has been accessed 22590 times at 72 hits per month. |
|---|