Although the proof Kempe gave for the Four Color Theorem (4CT) in 1879 was flawed, the methods he devised were still useful. In 1890, Heawood used a modification of Kempe's methods to prove that planar graphs can be five-colored (see [6] and [4]). (All graphs here will be assumed to have no loops and no parallel edges.)

In a 1968 paper ([5]), Stephen Hedetniemi used modifications of Kempe's ideas to show, among other things, that every planar graph can be decomposed into the edge disjoint union of three bipartite graphs.

My purpose in this note is to make the observation that a stronger result is now possible, namely

Proposition A. Every planar graph can be decomposed into the edge disjoint union of two bipartite graphs.

It is not surprising that Hedetniemi did not obtain the result of Proposition A, since Proposition A is equivalent to the Four Color Theorem, the proof of which was announced in [1](1976).

So as much as I would prefer to prove Proposition A directly, I am able only to cheat the reader by proving instead the elementary

Theorem A. Proposition A is equivalent to the Four Color Theorem.

Proof. Assuming the 4CT, let a planar graph G =(V,E) with vertex set V and edge set E be four-colored using for colors the ``ordered pairs'' aa, ab, ba ,bb. (See the example in figure 1.) Let G<sub>1</sub>=(V,E<sub>1</sub>) and G<sub>2</sub>=(V,E<sub>2</sub>), where the edges in E<sub>1</sub> are chosen to be those edges in E of the form {aa,ba}, {ab,bb} and {ab,ba}, and the edges in E<sub>2</sub> are the remaining edges, namely those colored {aa,ab}, {ba,bb} and {aa,bb}. Observing that the vertices of the edges in E<sub>1</sub> have colors differing in the first component, we can now drop the second component, leaving the graph G<sub>1</sub> two-colored in the ``colors'' a and b. Similarly, we drop the first component in G₂ to obtain a two-colored graph. (Clearly, other partitions of E which accomplish this are possible.) Being two-colored, the graphs G₁ and G₂ are bipartite.¹

Conversely, we can take two edge disjoint bipartite graphs (having the same vertices) and two-color each using the colors a and b. Their union will then be four-colored by the resulting ordered pairs aa,ab,ba,bb. à

A natural question is whether such a ``bi-bipartite'' decomposition is always possible with the additional property that G₁ has no cycles and G₂ has only cycles. To put it more precisely, can the two graphs be bipartite, with G₁ a forest and G₂ containing no isthmus ²? This will be left for the interested reader to ponder.³

It is evident that more vertices in G₁ and G₂ can be joined, still leaving each two-colored, though G₁ and G₂ would no longer be edge disjoint. Joining all possible vertices in this fashion corresponds to adding to each of these graphs the edges in G of the form {aa,bb} and {ab,ba}. Let G¢₁ and G¢₂ be the graphs formed from G₁ and G₂, respectively, by adding all these edges (see figure 2). Clearly, G¢₁ and G¢₂ are each bipartite and consist of those edges in G whose colors differ in the first and second components, respectively.

With just a bit more work, we can show that if G is a plane triangulation with more than three vertices, then no edge in G¢₁ or G¢₂ will be an isthmus. Thus, each edge in these two graphs will be part of an even circuit in that graph, but not part of any odd circuit.

Theorem B. The Four Color Theorem is equivalent to the proposition that every planar triangulation with more than three vertices is the union of two connected bipartite graphs, each with no isthmus.

Proof. Assume the FTC is true and form G¢₁ and G¢₂ from G as described above. Clearly, each of G¢₁ and G¢₂ is connected and has no odd cycles, since they are each 2-colored by the first and second components, respectively, of the colors of G. It remains only to show that neither G¢₁ nor G¢₂ has an isthmus. It suffices to show that an arbitrary edge xy in G¢₁ is always contained in a quadrangle (4-cycle) in G¢₁.

Let xyu be a triangle in G. Since the first components of the colors of x and y differ, the first component of the color of u must differ from one of these, so either xu or yu is an edge in G¢₁. Losing no generality, we'll say that xu is in G¢₁. Now the edge yu, whose vertices have identical first components, must be part of another triangle yuv in G. But then v has a color whose first component differs from that of y and u, so the edges yv and uv are in G¢₁. So now we have the quadrangle xyvu in G¢₁ and we're done.

The converse is clear, by the same argument as in Theorem A. à

The proof above suggests another formulation of Theorem B, namely: the Four Color Theorem is equivalent to the proposition that every planar triangulation with more than three vertices is the union of two planar quadrangulations. But now I'm taking too many liberties with the terminology and merely restating the (ahem) four-gon conclusion!

Incidentally, in [5] it was also shown that every planar graph can be decomposed as the edge disjoint union of at most three forests. Our four-color approach can certainly not improve that result, since even the simple example G in figure 1 cannot be decomposed into two edge disjoint forests.

For nonelementary results concerning even circuits in planar graphs, the reader can consult [7] and [9].

Bibliography

[1]

K. Appel and W. Haken, Every planar map is four colorable, Bull. AMS, 82 (1976) no. 5, 711-712.

[2]

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Pub. Co., New York, NY, 1976.

[3]

N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, NJ, 1974.

[4]

P. Heawood, Map colour theorem, Quart. J. Pure Appl. Math., 24 (1890) 332.

[5]

S. Hedetniemi, On partitioning planar graphs, Canad. Math. Bull., 11 (1969) no.2, 203-210.

[6]

A. B. Kempe, On the geographical problem of the four colors, Amer. J. Math., 2 (1879) 193-200.

[7]

P. D. Seymour, Even circuits in planar graphs, J. Comb. Theory (B), 31 (1981) 327-338.

[8]

P. D. Seymour, private communication, (1994).

[9]

C. Q. Zhang, On even circuit decompositions of Eulerian graphs, J. Graph Theory, 18 (1994) no. 1, 51-57.

[10]

C. Q. Zhang, private communication, (1994).

Footnotes:

¹This ``color-decomposition'' idea has undoubtedly been observed by many. I discovered it as I was preparing a presentation on the history of the 4CT for an introductory graph theory course I attended as a graduate student in 1982. In the intervening years, I never saw the result in print. By chance, I recently saw the above cited paper of Hedetniemi, which renewed my interest. Since I am not a graph theoretician, I thought it wise to consult an expert. My victim was C.Q. Zhang at the University of West Virginia, who turns out to have discovered the exact same proof ([10]), also as a graduate student, and also has not seen it in print. Zhang also pointed out that Hedetniemi's result for three bipartite graphs can be accomplished in the same way, as a corollary to the 5CT: take aaa, aab, aba, abb, baa as the five colors and use the three components.

²An isthmus is an edge whose removal disconnects the graph. This is sometimes the definition given for the term bridge, e.g., in [3,p.286], but that term has other meanings, as in [2,p.145].

³ Paul Seymour has a nice solution to this problem ([8]), which I will divulge to the reader privately, upon request.