PROGRAMMING TIPS

Four-Coloring Planar Maps

Mathematica can be used to illuminate one of the most famous false proofs in history: Kempe’s 1879 “proof” of the four-color theorem. Moreover, combining Kempe’s ideas with some sophisticated Mathematica functions seems to yield a fast algorithm for four-coloring planar maps.

by Joan P. Hutchinson and Stan Wagon

One of the impressive features of Mathematica is its breadth. The user who is familiar with the diverse functions in its standard packages is more likely to use those functions when the need arises. In this column we describe the important role that several such functions played in our development of a comprehensive package to deal with issues surrounding the four-color theorem. In particular, the graph manipulation functions from the Combinatorica package and the DelaunayTriangulation function from the ComputationalGeometry package were instrumental to the development of the GraphColoring package that we describe here. And, as often happens, thinking hard about real-world implementation problems leads to new ideas and ways of looking at things. It now seems to us that Kempe's false proof of the four-coloring theorem is the best way to actually four-color planar graphs in practice!

The package on which this article is based is described in more detail in the forthcoming Mathematica Explorer project by the second author [Wagon, in press].

.  COMBINATORICA

To understand what Mathematica can do regarding coloring planar graphs and maps, the reader will need a rudimentary knowledge of Combinatorica, the standard package that has many functions for dealing with graphs. Abstractly, a graph is a set of vertices and edges, where each edge is a pair of distinct vertices. The adjacency matrix of an n-vertex graph is the n×n matrix of 0's and 1's that tells which vertices are joined by an edge. In Combinatorica a graph is represented by the adjacency matrix along with locations of the vertices for a drawing in the plane as follows: Graph[adjmat, vertices]. Such a representation allows the graph to be drawn very quickly using straight lines for the edges, but no attempt is made to avoid edge-crossings, even if the graph is planar. One views the graph via ShowGraph. Figure 1, for example, shows the complete bipartite graph (Subscript[K, 3, 3]), also known as the gas-water-electricity graph because of the ancient puzzle of connecting three houses to three utilities with no crossings.

Needs["DiscreteMath`Combinatorica`"]

ShowGraph[CompleteGraph[3, 3]];

The Graph itself consists of the matrix and the six vertex locations.

CompleteGraph[3, 3]

%[[1]] // MatrixForm

And here is the complete graph on four vertices.

ShowGraph[CompleteGraph[4]];

Combinatorica contains many functions for working with graphs; the user should consult either the package book [Wolfram Research 1996] or Steven Skiena's guide to the package [Skiena 1990] for more details. For example, there is a VertexColoring function, which uses a heuristic method due to Brélaz to color the graph so that adjacent vertices have different colors.

VertexColoring[CompleteGraph[3, 3]]

The heuristic did well in this case, since the graph is bipartite and so is indeed 2-colorable. In general, however, this method does not always succeed in coloring planar graphs with four colors.

In our package, called GraphColoring, we implement PlanarGraph objects. This is a data structure identical to Graph[a,v], with the restriction that the straight-line drawing inherent in the vertex locations has no crossings. It is therefore critical that programs that produce PlanarGraph objects should always ensure that the output meets the planarity criterion. For example, we made DeleteVertex work with PlanarGraph objects, but not AddVertex. To blend PlanarGraphs in with Combinatorica we simply used many lines of the following form.

Unprotect[func]func[g_PlanarGraph]  :=  func[Graph @@ g]Protect[func];

This works for functions such as V[g], which counts the number of vertices in a graph g. For a function such as DeleteVertex, the output should be a PlanarGraph object, so the code is different: we use Apply (or @@) to turn g into a Graph, use Combinatorica's DeleteVertex function, and then turn the result into a PlanarGraph.

DeleteVertex[g_PlanarGraph,  v_] :=  
      PlanarGraph @@ DeleteVertex[Graph @@ g,  v_]

.  MATHEMATICAL MAPMAKING

We summarize here the main functions of our package that are relevant to the four-color theorem, together with notes on implementation. The reader surely knows that the four-color theorem asserts that every map drawn in the plane can be colored using four colors, where countries that share a border segment must be colored differently. The problem was posed in 1852 by Francis Guthrie (see [Biggs, Lloyd, and Wilson, 1976]). Alfred Kempe published a proof in 1879. Quoting Biggs et al: “[This is] probably the most famous fallacious proof in the whole of mathematics....The supposed solution was greeted with great enthusiasm...we must presume that Kempe's argument was generally accepted as correct.” But, alas, the argument was badly flawed, though this was not observed until 1890 by P. J. Heawood, who showed that Kempe’s “chains” got irreparably tangled for some examples. We will discuss the method in detail in section 4. In 1976 K. Appell and W. Haken of the University of Illinois proved the four-color theorem, using computers to generate and examine almost 2000 cases.

Because Mathematica’s graphics capabilities are so strong, we use them to display actual maps. We did this via PlanarMap objects. Such an object, like Graph, has two arguments: the second is the list of points in the plane that define the countries; the first argument is the set of lists of indices of points that define each of the faces, in counterclockwise order. Here is an example that we built by consulting and massaging the data in Mathematica’s standard WorldData package.

Needs["GraphColoring`"]

Short[MapOfWesternEurope,  10]

For map viewing, we defined ShowMap (our functions have many more options than we shall discuss here; the reader is encouraged to browse the package via Options[func] and usage messages). Figure 3 contains the result of the following command.

ShowMap[MapOfWesternEurope, CountryColors -> GrayLevel[0.7], 
      Background -> White];

Of course, this map can be colored in four colors. It cannot be done with three colors. Can the reader see why?

To illustrate the ultimate power of the package, even though we have not yet discussed exactly how one colors a map or graph, note that the FourColorCountries option can be used to call our FourColoring function and then color the countries according to the result.

\(\(ShowMap[MapOfWesternEurope, 
	FourColorCountries -> True, 
	
      CountryColors -> {White, GrayLevel[0.35], GrayLevel[0.75], Black}, 
      Background -> White, 
      BorderPointStyle -> AbsolutePointSize[2]]; \)\)

With some help from Tom Whitesides (Kodak), we were able to efficiently define the U.S. states using only 151 data points, and the map is included in the package.The image is rough, but it does include all the adjacencies needed to consider the coloring problem. We will do that in section .

ShowMap[MapOfUSA, Background -> White, 
      CountryColors -> White, BorderPoints -> None];

For every plane map there is a related planar graph, whose vertices correspond to the countries and with two vertices connected by an edge when the corresponding countries share a border. We have a PlanarMapToDualGraph function, though getting the graph so that the embedding is indeed planar is tricky. Indeed, we have not attained perfection on that score! First, an example.

\(\(Show[
      Block[{$DisplayFunction\  = \ Identity}, 

        	{ShowMap[MapOfWesternEurope, CountryColors -> White, 
            BorderPoints -> None, Background -> White], 
	\ 
          ShowGraph[PlanarMapToDualGraph[MapOfWesternEurope], 
            VertexSize -> AbsolutePointSize[3]]}]]; \)\)

This seems to have worked fine. Each vertex is inside its country and all edges that should be there are there. Convex or nearly convex countries are easy: just use the centroid of the border points. But nonconvex countries present a difficulty. In those cases we triangulated the polygon using interior diagonals (code for doing that appears in Chapter 10 of [Wagon 1991]) and then used the centroid of the largest triangle. This places the dual vertex inside the polygon, but there is really no guarantee that the edges that result will not cross. If the countries are extremely convoluted polygons, then the edges might well cross. Indeed, there does not seem to be a simple way around this. Thus PlanarMapToDualMap is capable of producing a PlanarGraph object that is not given as a planar embedding. Fortunately, examples of interest tend not to involve convoluted countries, and this issue has not caused any problems for us yet.

Because we wished to show graphs with their vertices colored, we introduced a special function to do that. It takes as a second argument a list of color-indices to be used on the vertices; the colors themselves are specified by the VertexColors option. We also use the standard notation K[n] to abbreviate CompleteGraph[n]. Since Combinatorica’s K[4] is not a planar embedding, we defined K4Planar. A nice set of colors is used by default, but for black/white work we must specify grays.

\(\(ShowColoredGraph[K4Planar, {1, 2, 3, 4}, 
	
      VertexColors -> GrayLevel\ /@\ {0, 0.25, 0.75, 1}, 
	
      Background -> GrayLevel[0.5]]; \)\)

Finally we mention two functions that can be used to generate examples. We can get a planar graph by generating random points in the unit square and using DelaunayTriangulation from the ComputationalGeometry package. This produces a planar graph where each face is a triangle. If greater face-diversity is wanted, there is a DeleteEdges option that will delete some edges. We use SeedRandom to reset the random-number generator.

\(SeedRandom[1]; 
ShowGraph[RandomPlanarGraph[10]]; \)

Getting planar maps is trickier. We start with random points and form a triangulation. Then we place a point at the centroid of each triangle that involves an interior point of the configuration and look at the map defined by those points and the lines obtained by connecting points whose defining triangles share a border. This is not the graph-theoretic dual map of the planar triangulation: that would involve additional exterior faces, which we wish to avoid, and we do so with the restriction to triangles with interior points. By resetting the random number generator, we get, in Figure 9, the map corresponding to the graph in Figure 8.

SeedRandom[1]; 
    ShowMap[g = RandomPlanarMap[10], CountryColors -> White, 
      BorderPoints -> False, Background -> White, 
      Frame -> False];

.  PROPERTIES OF PLANAR GRAPHS

A critical observation in just about all work on planar graphs is that such a graph must have a vertex of degree at most 5 (the degree of a vertex is the number of vertices to which it is adjacent). Here is a proof starting from Euler's formula, which states that v + e – f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces, counting the exterior as a face.

Let sum denote the sum of the degrees and let avg be the average degree over the vertices. Then we know four facts about these quantities:

1.   v – e + f = 2  (Euler's formula)
2.  avg = sum/v
3.  sum = 2 e (each edge gets counted twice when we sum the degrees of each vertex)
4.  3 f  ≤  2 e  (each face is at least 3-sided and counting edges around faces counts the edges twice)

We can prove that the average degree is less than 6 as follows. First we turn inequality (4) into an equality by adding a variable that we will know is nonnegative. Then Reduce can be used to replace the system by an equivalent one with avg isolated and e, f, and sum eliminated.

\(r\  = \ 
      Reduce[{v\  - \ e\  + \ f\  == \ 2, 

          		\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ avg\  == sum/v, 

          						\ \ \ \ \ \ \ \ \ \ \ \ sum\  == \ 2\ e, 

          		\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
          3  f\  + \ w\  == \ \ 2\ e}, avg, \ {e, f, \ sum}]\)

We now subtract avg from 6.

6 - r[[2, 2]]  // Simplify

This is positive so the average degree is strictly less than 6. This proves the following critical property of planar graphs: Every planar graph has a vertex of degree 5 or less.

Of course, there remains the question as to why Euler's formula is true. With some guidance from us, Mathematica can essentially prove it. If the graph has a cycle, remove it. This decreases each of e and f by 1, and so leaves v – e + f unchanged. If the graph has no cycles, it is a tree and one can remove a vertex of degree one and its edge. This reduces v and e by 1, and so leaves v – e + f unchanged. When the tree is completely chopped down, only a single point remains; then v = 1, e = 0, and f = 1. But 1 + 1 = 2. QED.

One can make a nice movie (it is in the package as EulerFormulaProofMovie and uses Combinatorica's FindCycle command) of how this sequence of operations turns a modest-sized map into a single point, with the plot label showing the status of v, e, and f along the way.

.  KEMPE AND THE FOUR-COLOR PROBLEM

Here is how Kempe, in 1879, proposed to solve the four-color problem. We will give his proof in the form of a recursive algorithm to color any planar graph using red, green, blue, and yellow. We assume the graph G is given with its vertices in some definite order.

Step 1. Let V be the first vertex of least degree; we know this degree is 5 or less.

Step 2. Delete V and its edges from G to get a graph (G^′) with fewer vertices.

Step 3. Use recursion to four-color (G^′); if (G^′) has one vertex, color it red.

Step 4. Find a color to assign to V so that the coloring is properly extended. This requires several cases.

   Case 1. The neighbors of V use three or fewer colors.
       This is easy. Assign the first free color to V.

   Case 2. The neighbors of V consume all four colors.
        Eliminate one of the colors by a "Kempe chain color switch". Then use that color on V.
        
Now, what exactly is a Kempe chain? The concept is simple and pretty. Suppose the colored ring around V consists of four vertices W, X, Y, Z that use all four colors (red, green, blue, yellow, respectively).  Then look at the W-Y pair and find all vertices that (a) are colored with either red or blue; and (b) are reachable from W via a path of red or blue vertices. This set of vertices, which includes W, is called a Kempe chain. If Y is not in the Kempe chain, we can just switch red and blue along the chain without an adverse affect on the overall coloring. The ring is then free of red, which can be used to color V. If the chain does reach Y we cannot switch colors. But then a green-yellow chain from X to Z must succeed (i.e., fail to reach Z), because the red-blue chain blocks this chain from reaching Z.
        
Consider the two examples in Figure 10, where the large white disk is the critical vertex, V. Suppose V is deleted and the remaining 14-vertex graph was colored as illustrated, where we use white disks, gray disks, black disks, and black squares for the four colors. The neighbors of V use all four colors but the Kempe chain from W to all vertices that can be reached from it among those colored either white or gray does not reach Y! So the Kempe chain is successful and all colors on the chain can be switched, white to gray and vice versa. This frees up white to be used on V. If the chain did reach around to Y, as happens in Figure 10(b), then a chain from X could not reach Z, and a color-switch on that pair would free up the black disk. So the degree-4 case is done.

(a)

In the case that V has degree 5, Kempe's reasoning is similar. In this case there must be a repeated color among V's neighbors. The repeated color might occur on two vertices that are next to each other in the order around V (the "adjacent" case), or the repeated color can be split (the "split" case). Here is Kempe's argument.

In the adjacent case suppose the situation is RGGBY. Try to chain from blue to red (i.e., check the blue-red chain from the blue vertex to see if it reaches red). If that fails, then a chain from yellow to the green pair must succeed. In either case, a color is removed. As for the split case, suppose the situation is (Subscript[RG, 1])(Subscript[BG, 2])Y. Try to chain from red to blue. If that fails, try to chain from yellow to blue. If both fail, then the two green/yellow chains out of green will work (i.e., fail to reach yellow), thus eliminating green (see the schematic in Figure 11). More precisely, chains from (Subscript[G, 1]) to yellow and from (Subscript[G, 2]) to red must both succeed, thus freeing up green to be used on V.

Thus, in all cases, a color is removed from the ring around G. This proves the four-color theorem . . . or does it?

We will not present examples of the degree-5 case here (the reader is encouraged to ponder the reasoning!), but they are included in our package. In fact, the package has an AlgorithmTrace option that creates a movie of the Kempe chain procedure, highlighting edges and chains as they are considered and illustrating the color switches that occur.

.  BUILDING KEMPE CHAINS

Our package is quite long and we will not go into many programming details here. A critical point discovered at a late stage was that the use of recursion, though easy to program, is extremely wasteful of memory. Reprogramming using iteration saved both time and memory. To give a flavor of some of the programming, we present one example, KempeChain1 (so named to avoid clashing with the package). The input is a planar graph in the form of adjacency lists (this is much more memory efficient than using a sparse 0-1 matrix), a pair consisting of a source vertex for the Kempe chain and a target vertex or vertices (since the target might be a pair), and a coloring list containing the colors of the graph. The output will be False if there is a Kempe chain from the source to the target; otherwise the output is a new coloring, with colors properly switched along the chain. The main FourColoring routine will call the Kempe chain routine many times as it builds the coloring up from a single vertex. Some careful accounting is needed to keep track of the vertex labels, because, when the AlgorithmTrace option is used to draw the graphs at each step, we need indices both in the main graph and in a subgraph.

• Neighbors is a customized function that gives the neighbors of a vertex having specified colors.

• The use of nofail and While allows us to halt chain-construction as soon as the target is reached, it it is reached.

• chain is the collection of specially-colored vertices that can be reached from v1: the Kempe chain. This is formed by simply looking at the specially-colored connected component of v1, built by using Union and Neighbors.
 
 • Local variables are not used. Tthe package already provides enough protection for variable names, via the `Private` context, so it is more efficient to avoide the use of Module.

The routine concludes by checking nofail. If it is False, the target was hit and False is returned to mark a failed Kempe chain; if not, the resulting True is replaced by the new coloring (the color switch being carried out by Scan and ReplacePart; note the use of “True :> ” as opposed to “True ->”, which is essential to avoid the evaluation of the right-side of the rule unless the substitution is actually carried out). This piece of code takes about the same number of characters as Kempe required to describe this part of his method in 1879!

Neighbors[adj_List, v_Integer, col_, goodcol_] := 
      Select[Flatten[{adj[[v]], v}], 
        MemberQ[goodcol, col[[#]]]&]

KempeChain1[gadj_, {v1_, vv2_}, coloring_List] := 
(answer = coloring;
 chold = {}; chain = {v1};
 While[(nofail = (Intersection[Flatten[{vv2}], chain] == {})) && 
    chain != chold,
 {chold,chain} = {chain, chain ⋃ Union @@ 
 (Neighbors[gadj, #, coloring, coloring[[Flatten[{v1,vv2}]]]]& /@
     chain)}];
 nofail /. True :> (Scan[(answer = ReplacePart[answer,
    Complement[coloring[[Flatten[{v1, vv2}]]],{answer[[#]]}][[
      1]], #])&, chain];
    answer))

Here is an example of how the code works, using the first example of Figure 12, which is stored in the package as KempeExamples[1], a pair consisting of a 15-vertex graph and a list that defines a precoloring of the first 14 vertices (with a 5 to mark the uncolored vertex).

g = KempeExamples[1][[1]]; 
    coloring = 
      KempeExamples[1][[2]]

KempeChain1[ToAdjacencyLists[ DeleteVertex[g, 15]], {1, 3}, 
      Drop[coloring, -1]]

A comparison shows that the colors have been switched for four vertices, including number 1, which is correct (see Figure 12).

Position[Abs[% - Drop[coloring, -1]], _?Positive]

As mentioned, I first used recursion to program Kempe's four-coloring ideas. But that failed badly on large graphs (in particular, the 341-vertex example in Figure 15). After all, a recursion asks for the kernel to keep track of each subgraph all the way down. It makes much more sense to program this algorithm iteratively. To give a flavor of the efficiency gain, consider the preliminary problem of getting the vertices ordered so that each one has degree 5 or less in the graph determined by the vertices that follow it in the order. Of course, this is easy to program recursively. But look at how simple a direct routine is. Take my word for it: this is much, much faster than a recursive approach!

We use the double pattern to catch both PlanarGraph and Graph objects. DegreeSequenceOrdered is in our package and differs from Combinatorica's DegreeSequence function in that it keeps the degrees in the order of the vertices. The main tricks are: using ∞ to mark the vertices that are already chosen, and subtracting 1 from various points in the degree sequence to indicate the deletion of a vertex. Ths subtraction is efficiently accomplished by subtracting the proper row of the adjacency matrix — g[[1, vert]] — since that consists of exactly the 0s and 1s that we want!

\(KempeOrder[g_PlanarGraph | g_Graph] := 
      Module[{degs = DegreeSequenceOrdered[g], vert}, 
        Table[vert = 
            First[Select[Range[V[g]], 
                degs[[#]] < 6&, 1]]; 
          degs[[vert]] = ∞; 

          			degs -= g[[1, vert]]; 
          vert, {V[g]}]]\)

There are several other issues regarding memory savings that arose when I tried to four-color a certain 341-vertex planar graph. For example, it is much more efficient to keep track of the adjacency lists, as opposed to the full adjacency matrix. Suffice it to say that the package contains optimized code that attempts to minimize the consumption of time and memory. The interested reader should look at the KempeChain function in the package to see how it compares to the first draft given above. Fortunately, a memory-smart program is usually faster too.

.  KEMPE’S CHAINS GET TANGLED

Heawood found a flaw in Kempe's argument. But his example required that certain vertices be precolored. When presented with certain precolored situtaions, Kempe's chains get tangled in a way he, and everyone else who read and appreciated his proof in the decade following its appearance, had overlooked. Our package allows the precoloring of vertices, and so can be used to demonstrate Heawood's type of example. But it is much more elegant to avoid the precoloring. Figure 12 shows an example (due to A. Errera) that tangles the chains that arise in Kempe's algorithm.

\(\(ShowLabeledGraph[KempeExamples[5], \ 
	DefaultColor -> White, 
      
	EdgeStyle\  -> \ Black, 
	LabelOffset\  -> \ 0, 
	
      DefaultFont\  -> \ {"Courier", \ 9}, 
	
      VertexSize -> AbsolutePointSize[13]]; \)\)

The reader might enjoy taking pencil in hand and following Kempe's argument through for this example. The first vertex of minimal degree (5), is vertex #1.

DegreeSequenceOrdered[KempeExamples[5]]

When that is removed, there are vertices of degree 4.

DegreeSequenceOrdered[g1  =  DeleteVertex[KempeExamples[5], 1]]

So vertex number 2 in the original labeling is the next one to go (it is the first vertex in the graph g1) and the reader can check that the vertices get removed in the order of the labels. So #17, the last one, is the first to be colored (it gets color number 1), and the other 15 vertices in g1 are colored in turn with no difficulty.

FourColoring[DeleteVertex[KempeExamples[5], 1]]

Now here comes the punch line! We are in the split case, and Figure 13 shows the situation, with the neighbors of V (#1) labelled with letters identifying their colors.

Figure 13 shows that the chain from B to Y is a failure because it reaches Y. Similarly the reader can see that the blue-red chain chain from B to R will reach R. So we now turn to chains out of the green vertices. The green/red chain from (Subscript[G, 1]) contains only two vertices, and fails to reach R, as it must fail in general in this case. But now here is the flaw: When the green/red switch along this chain is made it breaks the earlier red-blue chain, and allows a green/yellow chain from (Subscript[G, 2])to slip through to Y! This was not supposed to happen, and is the reason Kempe's proof breaks down.

Presumably this 17-vertex example is the smallest counterexample, but we have not tried to prove that.

.  THE UNDERLYING SOUNDNESS OF KEMPE’S IDEAS

Kempe's ideas, though flawed, should not be lightly dismissed. First, they have played an important role in later work on the four-coloring theorem. Kempe's proof can be summarized with two main points.

1. Every planar graph contains one of the following configurations: a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, or a vertex of degree 5. This is a set of unavoidable configurations.

2. Each configuration in (1) is reducible in the sense that, if the remainder of the graph can be colored, so can the configuration.

Assertion 2 is false. But Appel and Haken's 1976 proof of the four-color theorem had the same basic organization, though with a list of 1936 unavoidable and reducible configurations. Recent work [Robertson et al, 1996, 1997] has yielded a proof using only 633 configurations.

Moreover, it seems that Kempe's ideas yield a fine algorithm for 4-coloring planar graphs provided one makes random choices at each step. The example that shows Kempe's method fails relies on a very precise ordering of its 17 vertices. Consider the following algorithm where the input is a graph that yields a planar embedding when straight lines are used to represent the edges.

1. Choose a random vertex of least degree, and remove it.

2.  Color the vertex-deleted graph by induction.

3.  Color the removed vertex as follows: if only 3 colors are used among its neighbors use the free color;  if its neighbors consume all four colors, use Kempe's color-switching method.

Compare this description with Kempe's own words on the subject [Biggs, Lloyd, and Wilson, 1976]:

“A practical way of colouring any map is this. Number the districts in succession, always numbering a district which has less than six boundaries, not including those boundaries which have a district already numbered on the other side of them. When the whole map is numbered, beginning with the highest number, letter the districts in succession with four letters, a, b, c, d, rearranging the letters whenever a district has four round it, so that it may have only three, leaving one to letter the district with. When the whole map is lettered, colour the districts, using different colors for districts lettered differently.”

All that we have done is make precise the way in which the numbering is to be done: use random choices. This is the algorithm we have implemented with the Randomize option to FourColoring. It has no trouble with the tangled-chains example, as the following code shows.

FourColoring[KempeExamples[5], Randomize -> True]

Well, as 9% of the readers who try it will find out, the algorithm can fail on this particular example! Those readers can simply try again. But more complex graphs that contain, somewhere within them, the essence of the counterexample will surely fail to foil our algorithm, for the chance of the random selections finding the bad subgraph in just the right order seems very small. And we have had no problems using this algorithm to 4-color random planar graphs with 100 or more vertices. Of course, we are now into the research zone. Does our algorithm work with probability approaching 1 as the number of vertices increase? This might be difficult to answer, since it requires measuring both the likelihood of a tangled-Kempe-chain subgraph and the likelihood of coming on such a subgraph in just the right order. A more important question is: Might there be a super-counterexample that foils the algorithm for all random choices? We conjecture that the answer is no.

.  APPLICATIONS

Since FourColoring (even without randomization) performs well in practice — it has never stumbled on hundreds of examples, with up to 200 vertices — we can have some fun and try to color the lower 48 states. A first question is whether this can be done in three colors. It cannot. The U.S. has no (Subscript[K, 4]), but there are two states that are difficult in a subtler way: Nevada has five neighbors. They require 3 colors, so Nevada needs a fourth. And Kentucky has 7 neighbors, so its vicinity needs a fourth color too. Our algorithm, however, yields eight states with the fourth color.

\(\(ShowMap[MapOfUSA, 
	FourColorCountries -> True, 
	
      Background -> GrayLevel[0.5], 
	BorderPoints -> None, 
	
      CountryColors -> \ GrayLevel\ /@\ {1, \ 0.75, \ 0.35, \ 0}]; \)\)

Can the seemingly inessential third use of the fourth color be eliminated? Yes, but we will not spoil the reader's pleasure by giving the solution. In fact it can be done, and the following code, which uses the precoloring option to force certain colors on Kentucky, Nevada, Ohio, and Pennsylvania, produces a solution.

\(\(ShowMap[MapOfUSA, FourColorCountries -> True, 
      BorderPoints -> None, 
	\ 
      Precolored\  -> \ {{15, 1}, {31, 1}, {33, 4}, {36, 3}}]; \)\)

As a final application, consider the graph in Figure 15 (due to E. F. Moore [Kainen and Saaty, 1977, p. 96]). Actually, that figure is not quite the full Moore graph, as there should be edges included from the left border to the right. Still, it is complicated enough. This graph is of theoretical interest because it has no small reducible configurations, and it was suggested that this graph is a good test of a 4-coloring algorithm. More to the point, it was an excellent test of my implementation, for the recursive method simply failed to work on it. The iterative approach gave a 4-coloring in about 45 minutes of CPU time, but it led to much sharpening of the program and the package now colors this graph in 8 minutes. The reader might enjoy trying to 4-color this 341-vertex graph by hand. The graph is in the package as MooreGraphPartial, and a correct coloring is returned by FourColoring[MooreGraphPartial]. The algorithm uses 50 Kempe switches as it builds up the coloring to all 341 vertices. The full Moore graph is included as MooreGraph.

ShowGraph[MooreGraphPartial];

.  CONCLUSION

It was very exciting to take 100-year old ideas, simple as they are, and implement them in Mathematica. As noted, it seems to us that Kempe's basic reasoning leads to a sound randomized algorithm for quickly 4-coloring planar graphs. But, as is often the case, there is more work to be done, both of a theoretical and practical nature. In addition to the open question about whether our algorithm really works on all planar graphs, there are further directions for computing innovations.

• Our package assumes that graphs are given in planar form with straight lines as edges (it is a theorem of Fáry and of Wagner that every planar graph has a straight-line embedding). But the data type could be expanded to include graphs with polygonal or curved edges. They would not look planar when drawn with straight lines, but the 4-coloring algorithm could be made to understand them and come up with 4-colorings, since it only needs to know the counterclockwise order of edges around each vertex.
 
 • Of course, this leads to the rich area of graph-drawing algorithms and the many difficult and intriguing questions there, such as: Given a planar graph, come up with a planar embedding using straight lines.

• And one can always look on other surfaces for a wider class of graphs and graph-coloring problems. Our package includes a ShowToroidalGraph routine that provides a rudimentary way of drawing graphs on the torus. Here is sample output that shows (Subscript[K, 6])embedded on  flat torus. In fact, (Subscript[K, 7]) can be embedded, and we leave that as an exercise. ShowToroidalGraph works like ShowGraph in that the first argument is a Graph object. But a second argument containing a list of edges and directions is necessary to specify which edges cross over the border. Specific edge styles can be given too, as is done below.

\(\(ShowToroidalGraph[
	
      Graph\ [Edges[K[6]], {{0.5, 0.35}, {1.15, 0.2}, {1.6, 0.35}, 

          			\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {0.4, \ 0.9}, \ \ {1.05, \ 0.7}, 
          \ {1.6, \ 0.8}}], \ 

      	{{3, 4, Right, {GrayLevel[0.5], \ AbsoluteThickness[4]}}, {1, 3, 
          Left, \ \ AbsoluteThickness[4]}, 

        		{1, 5, Down, \ \ AbsoluteThickness[4]}, 

        		{1, 6, Down, 
          \ {AbsoluteDashing[{4, 6}], 	\ AbsoluteThickness[2]}}, 

        	\ \ \ {2, 6, Down, \ {GrayLevel[0.5], \ AbsoluteThickness[4]}}, 
        \ \ \ \ \ \ \ \ {4, 6, Left, \ \ AbsoluteThickness[2]}}, 
	
      EdgeStyle\  -> \ AbsoluteThickness[2.5], 
	
      IdentificationArrows -> False, 
	
      Background -> GrayLevel[0.9], 
	
      VertexStyle -> {AbsolutePointSize[16], White}, 
	\ 
      TorusRange -> {2, 1}, Labels -> True, \ 
      LabelOffset -> 0]; \)\)

It is noteworthy that for surfaces with g holes, g > 0, it has been known since Heawood's work of 1890 that one can always color a graph on the g-holed torus with  \(TraditionalForm
      \`⌊\(7\  + \ \@\(48  g + 1\)\)\/2⌋\) colors. That this is best possible was proved in 1968 by Ringel and Youngs; the proof is difficult, but not as difficult at that of the 4-color theorem, which shows that this formula is valid when g = 0.

REFERENCES

BIGGS, N., E. K. LLOYD, and R. J. WILSON, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976.

KAINEN, P. C., and T. L. SAATY, The Four Color Problem, Assaults and Conquest, McGraw-Hill, New York, 1977.

ROBERTSON, N., D. P. SANDERS, P. SEYMOUR, and R. THOMAS. A new proof of the four-colour theorem, Electronic Research Announcements of the American Mathematical Society, 2 (1996) 17–25.

ROBERTSON, N., D. P. SANDERS, P. SEYMOUR, and R. THOMAS. The four-colour theorem, Journal of Combinatorial Theory, Series B (1997) (to appear).

SKIENA, S. Implementing Discrete Mathematics, Addison-Wesley, Reading, Mass., 1990.

WAGON, S. Mathematica in Action, W. H. Freeman, New York, 1991.

WAGON, S. The Mathematica Explorer, Wolfram Media. Inc., Champaign, Ill. (in press)

WOLFRAM RESEARCH. Mathematica 3.0 Standard Add-On Packages, Wolfram Media, Champaign, Ill., 1996.

ABOUT THE AUTHORS

Joan Hutchinson is a professional graph colorer, but specializing in graphs on nonplanar surfaces such as the torus. Recently she was able (with K. L. Collins) to prove a 4-color theorem for special graphs on the torus — the theoretical result was obtained in part by running Mathematica programs on specific examples until coloring patterns leapt from the output. She teaches courses in calculus, discrete mathematics, combinatorics, and computational geometry that use Mathematica intensively. Until now she has carefully avoided the four-color disease, but now this paper's conjecture on randomized Kempe coloring is starting to afflict her.

Joan Hutchinson
Department of Mathematics and Computer Science
Macalester College
St. Paul, MN 55105
hutchinson@macalester.edu


Stan Wagon uses Mathematica extensively in his research, teaching, and exposition and is especially appreciative of the new ways in which Mathematica allows us to look at mathematical objects. He is author or coauthor of several books, including Mathematica in Action, Animating Calculus, VisualDSolve, and Which Way Did the Bicycle Go?. He also teaches a high-altitude Mathematica course every summer in the mountains of Colorado.

Stan Wagon
Department of Mathematics and Computer Science
Macalester College
St. Paul, MN 55105
wagon@macalester.edu

ELECTRONIC SUBSCRIPTIONS

Included in the distribution for each electronic subscription are the files 4ColorTheorem.nb and GraphColoring.m containing Mathematica code for the material described in this article.