Three Trees Suffice

The 4-color theorem is equivalent to the fact that there is a locally injective function on the vertex set V of a 2-sphere. The reason that one can restrict to 2-spheres is that every planar 4-connected graph is part of a 2-sphere and that if a planar graph is not 4-connected, one can color each component and glue these components. A 2-sphere is a graph for which every unit sphere is a circular graph with 4 or more elements (having a circular graph of 3 elements as a unit sphere would mean we have a K4 subgraph and so a 3 dimensional object). The characterization of these graphs as maximally planar 4-connected graphs is due to Whitney from 1931.

[I myself started to get interested in graph coloring more than 10 years ago (see for example this video or this document) and still think that a geometric coloring algorithm will lead to a linear time constructive coloring. I have written about this extensively but here is a short unfinished write-up last edited 2019 [PDF]. The proof still needs to be implemented in a concrete way and can color a 2-sphere in polynomial time. Graph coloring is a fascinating area of mathematics. I myself am not so interested in the chromatology of “embeded graphs”. One can for example embed a K7 into a 2-torus which has little to do with the 2 dimensional nature of a 2-torus. A conjecture of Albertson and Stromquist from 1982 asks whether the chromatic number of a 2-torus [now meaning a graph where every unit sphere is a 1-sphere (circular graph with 4 or more elements)] is 5 or less. I proved once the upper bound for general d-manifolds, graphs for which every unit sphere is a (d-1) sphere. So, 2-manifolds can be colored with 6 colors. We do not know of any 2-manifold what needs 6 colors. When I started to working on this, one of the first things Jenny Nitishinskaya found in that summer was a projective plane with chromatic number 5. See also this video about geometric coloring.]

The ideas of the proof of the Haken-Appell proof of 4-color theorem are rather simple: assume there is a counter example, then use a reduction argument to show that one can make it smaller. Two main ideas: the reduction idea and Gauss-Bonnet was already known to George Birkhoff: The Gauss-Bonnet formula (essentially already known to the blind mathematician Victor Eberhard and used already for graph coloring by Birkhoff) tells that the sum of the curvatures add up to 2 for a 2-sphere.

[To repeat myself again: This is a special case of the general curvature for arbitrary graphs which add up to the Euler characteristic which by integral geometric considerations can be shown to produce the Gauss-Bonnet-Chern curvature for even dimensional manifolds but which of course is much more general than for manifolds. The general Gauss-Bonnet formula holds for all graphs and its proof is almost tautological: just shove the energy of a simplex in the graph $latx G$ equally to all the vertices in $latx x$. The reason why it produces the known curvature (using the Pfaffian of the Riemannian curvature tensor) in the continuum is because the curvature is the expectation of the Poincare-Hopf indices when taking the expectation over all random functions on vertices. In the continuum, the Gauss-Bonnet-Chern integrand is the index expectation too when averaging over all Morse functions obtained from linear functions on an ambient Euclidean space into which the manifold was embedded. That the Gauss-Bonnet-Chern integrand is the only “rotationally invariant” (meaning the symmetry group of the orthogonal frame bundle of the manifold) local quantity which adds up to Euler characteristic shows then the Gauss-Bonnet-Chern result. Using the Nash embedding theorem is of course a hack. With the Nash embedding theorem, the Gauss-Bonnet-Chern result had already been found before Chern. Chern was the first who did an intrinsic proof not requiring any embedding in an ambient Euclidean space]

There must be degree 4 or degree 5 vertices therefore. Degree 4 vertices can be dismissed quickly using Kempe chains as can degree 5 vertices if one wants to 5 color (Kempe’s proof led already to the 5 color theorem). But Alfred Kempe’s argument to reduce degree vertices fell short. It needed a sophisticated computer assisted search which was a brutal race and a bit unfair to Heesch as he was struggling with funding to get the computer power needed. The front runner Heinrich Heesch in that race eventually lost to Haken and Appell. The original Kempe’s proof attempt from 1879 was shown in 1890 to be flawed. Less well known is that William Story already pointed out caution about the proof in 1879, published in the same journal.

Since last fall, triggered by the passing of Frank Josellis, I got interested again in Lusternik-Schnirelmann stuff. A graph has category k, if there are k contractible subgraphs which cover it. This is related to arboricity which asks how many 1-dimensional contractible subgraphs (a fancy word for trees!) cover the graph. For one dimensional graphs, the arboricity and the categegory is the same. In that case the category is 1 for trees and 2 otherwise. For two dimensional graphs, meaning graphs without subgraphs, the category is less or equal to 3. the category of 2-spheres is 2 as we can cover it by two 2-balls. What about the arboricity? The Nash-Williams formula quickly shows that small examples like the octahedron or icosahedron need 3 trees: for the octahedron, and for the icosahedron . Using Gauss-Bonnet, Dehn-Sommerville and Nash-Williams one can quickly show that the arboricity of a 2-sphere is at least 3. I showed this again in this video from last week: Gauss-Bonnet and (trivial case of much more general) Dehn Sommerville show that the Euler characteristic is clashes with Nash Williams for . What about the upper bound.? How do we show that three trees suffice?

When recording the video last week, I was still under the impression that one can just modify the edge 3-coloring obtained from a vertex 4-coloring to modify the 3 Kempe chains (swap colors) to render them to be trees. The idea is simple: just cut the loops (by swapping two edge colors) one by one until we have a tree. What happens if we do these clippings is that we can combine for example 1-2 Kempe chains with 3-4 Kempe chains (which have the same color but were originally disconnected). No big deal I thought: just modify then also possible newly emerged large scale loops by clipping them. That still seems to work but then we get in general even larger scale loops combining clipped large scale loops. Then I asked myself, what this proof would show in the case of a 2-torus? The simplest 2-torus graph we can build has 16 vertices, 48 edges and 32 triangles. The Nash-Williams functional gives an upper bound for the arboricity and we can cover the torus with 4 trees. But we can also 4-color this torus. Now, if I apply the local modification proof to the torus, it would show that a 2-torus can be covered by 3 trees. This is obviously not working. Somewhere in the proof, a global property like simply connectivity of the 2-sphere or the Jordan curve theorem must appear. In other words, the proof that three trees suffice must be a global proof, not a local one.

The proof that three trees suffice also is a reduction argument. I like to think of it as a geometric deformation argument. We define an energy for every , where is a 4-coloring of the 2-sphere G. This energy depends on the coloring too and is the smallest area which a Kempe loop can see. If the energy is zero, then the 4-coloring of the vertices produces a 3-coloring of the edges and each of these colored subgraphs are trees. In the case when the energy is positive, we apply the geometric heat flow to make the energy smaller. but keep it positive and also does not decrease the arboricity (any k covering of the shortened graph can be extended to a k covering of the original graph). We show then (as usual in geometric flow analysis like the curve shortening flow in differential geometry) that there is an understood limiting situation, which is in our case the octahedron. The octahedron has arboricity 3 so that also any graph in the basin of attraction has arboricity 3. And these are all graphs which have positive energy. Note that many of these graphs of positive energy could be recolored to have zero energy. The energy depends not only on the geometry but the 4-coloring chosen. There are many graphs, like prims graphs which can not be recolored to have zero energy, but many graphs appear also to allow for a recoloring where the energy is zero. One can define an energy for 2-spheres which is the minimal energy one can have for a 4-coloring. (I simplified a bit the notion of energy. One has first to look at positive energy (the area of the inside of the loop) and minimize that, then look at the negative energy (the area of the outside) and minimize both If both are minimal 4, we have an octahedron. The octahedron graph is the unique minimum of the energy functional. This is no surprise given that it is the smallest 2-sphere overall. But to verify the minimal energy statement one has to check that no coloring with 0 energy is possible. Indeed, every 4 coloring must have a Kempe chain. If we color with 3 colors, every unit sphere is a Kempe chain. When 4 coloring the octahedron, there must be a pair with opposite colors, but then, the rest must be a Kempe chain as only 2 colors remain.

The task therefore is to have a nice heat flow on 2-spheres which has the property that it decreases the energy strictly and preserves the arboricity. The two reductions we can use are kite collapses (suck the air out of an embedded kite graph) and edge collapses (suck the air out of an embedded wheel graph with boundary length 4). For the edge collapse we reduce the degree of 2 boundary vertices, so that we have to reduce chains of wheel graphs which I call diamonds. For the kite collapse, we can only do that if the two opposite vertices have the same color. We call this a Heawood kite. The heat flow we do is not only working on the geometry, it also must be compatible with the coloring. If the energy of a colored graph is possible, then there is such a Hewaood kite. Actually, if the length of the Kempe loop is larger than 4, we can take a Heawood kite on the curve and shorten the loop. But there could still be a billion vertices inside that loop. We have then to make sure that there are Heawood kits in the interior. This follows from the fact that if we have a Kempe loop, then the rest of the same colored Kempe chain inside must have a leaf inside (if there is at all something inside). The reason is that otherwise, we would have a smaller loop formed inside.

So, to summarize. The proof consists of defining a geometric flow on the space of positive energy colored 2-spheres and show that if the energy is positive and the graph is different from an octahedron, the modified graph has strictly smaller energy and larger or equal arboricity. This shows then that every positive energy graph is attracted by the octahedron and because the octahedron has arboricity 3 also the original starting graph G has arboricity less or equal than 3.

It had been a beautiful day for flying. The last picture shows a bit of a damaged finger of mine. I had in the morning finished re-tiling part of our bath. There had been two tiles falling off and when I tried to fix that early in the week, half of the shower wall crumbled. The 70 year old house shows its age and there had been water damage behind the tiles. I removed that part of the wall, put new wood inside, then tiled it back. Working on a house is a bit like working in math. Sometimes, you try to fix something seemingly small and it turns out to be a bigger problem, requiring more work. In the case of our bathroom, we definitely will at some point put a completely new bath. Fixing the wall already was a hack, requiring to solve some puzzle. I had still some wood from fixing the stairs and almost magically could make it fit. The stuff behind the tiles is essentially fallen to dust (also in the tiles above) but I do not have time to remodel the entire bath now. its much nicer working on covering graphs with trees than covering an old bathroom with tiles in an old 70 year old house that had never been renovated completely (I only re-tiled the floor twice, replaced the lavatory and the sink myself).