Arboricity of Surfaces

We made an other attempt for getting elegant proof of the folklore theorem that the arboricity of a planar graph is maximally 3. The theorem has been stated in a paper of Algor and Alon in 1989 in the context of star arboricity. It appears in general to be “obvious”. I originally got to it by deriving it from my acyclic 4-color result telling that a 2-sphere can be acyclically colored with 4 colors if it is not a prism. I showed in general that the arboricity is smaller or equal than the acyclic chromatic number (a result of Hakimi, Mitchem and Schmeichel) and improved by 1, in the case when the acyclic chromatic number is even. This implies that all 2-spheres can be covered by 3 forests. This in turn implies the theorem of Algor and Alon that the arboricity of a planar graph is 3 or less. I had earlier asked the google “Bard” which thought the result is known without giving a reference (this had prompted me to look up the literature more carefully and I found the exercise in Bondi-Murty). Chat GPT 4 gave, when pressed for a reference the paper of Nash-Williams of 1964 but that one page paper does not prove this result. It definitely is a “hallucination”. (By the way, hallucinations are by far not new in AI. Humans do it all the time. Scientists often hallucinate if they do not know well. Everybody does that and it actually has some benefits as it prevents thinking blocks. If you would every time you are not sure stop, you would not move ahead fast enough to see larger connectons).

In this talk, I first of all note that it is quite easy to see that the Nash-Williams ratio E/(V-1) is smaller than 3 if the graph is a 2-sphere. The reason is that the f-vector (V,E,F) of a 2-manifold is completely determined by its area once the Euler characteristic is known. Using the same letters V,E,F for the cardinalities of the sets V,E,F is quite common when talking about planar graphs and I do this also here to prevent having to write absolute signs for cardinality all the time. Having the Nash-Williams ratio smaller than 3 for the entire graphs does does not prove the result because some subgraph might have a larger Nash-Williams ratio. Algor and Alon state the stronger statement that E is bounded above by 3V-6 but that requires to have V sufficiently large as the planar graph K2 shows. The task remains: how does one see so quickly that E is bounded above by 3V-3 for all planar graphs different from K1? It does not appear obvious to me (but I just might miss something). In the talk, I make an attempt. Here is an other attempt of this “folklore theorem” telling that the arboricity of a planar graph is 3 or less. We know that E/(V-1) is bounded above by 3 for a 2-sphere (a maximal planar 4-connected graph). This implies that it is true for any maximal planar graph. It follows then of course for any subgraph which has the same vertex set V because this makes E just smaller. But that is not enough: the point of Nash-Williams however is that it needs to be true for all subgraphs H of G which generate themselves. These subgraphs have a smaller vertex set therefore and it appears (at least to me and I still might just miss something obvious) not clear that the functional E/(V-1) is automatically bounded above by 3 also. I indeed believe it is very plausible that the functional which assigns to a subset W of the vertex set the Nash-Wiliams ratio where E(W) is the edge set generated by W takes it maximum at W=V. The intuition is that this is definitely a “local maximum” as we add a large chunk of edges when filling in the last vertex of a manifold.

I usually prepare for these Saturday’s (“talk to myself sessions” how my family jokes about these gigs, and indeed it is actually quite hilarious to talk alone to a camera) the night before or in the early morning just before biking in. In this case, I changed things while writing down the board and tried to go with the Algo-Alon inequality mentioned in their paper only noticing shortly before talking that it fails for small graphs like K2. I actually start to be believe now that the inequality was a typo in their paper and that they wanted to write which is the Nash-Williams bound and which holds for all planar graph. Still, how does one verify this? Here is a possibility:

Call a planar graph critical if is a minimal planar graph of arboricity 4. This is a notion adapted from terminology by Nash-Williams (who of course is inspired by the corresponding notion for chromatic considerations). We want to show that there is no such graph. Let G be a graph obtained by removing a vertex from a critical graph. By definition this graph has arboricity 3 or less and so a Nash-Williams ration . We can assume without loss of generality that it is 4-connected as otherwise, we can split the graph into 2 smaller components both of arboricity 3 and one of them would be critical. This means in particular that all vertex degrees are 4 or larger. There can be no leaves for example or K4 subgraphs. All faces of this graph now are “polygons” of length 4 or larger. Now, with E/(V-1) smaller than 3, adding a new vertex for a face and connecting it to the boundary adds m=4 or more points to the edge set and only 1 point to the vertex set. since (E+m)/V is larger than E/(V-1) we see that adding such a new “star” only can increase the Nash-Williams ratio. Now do this for all faces until we have a surface! In each step we have increased the Nash-Williams ratio. In the end, when we have a surface we have however a Nash-Williams ratio smaller than 3 (as we have computed before from the explicit f-data given by the area F alone. This argument shows that also the critical graph G must have Nash-Williams ratio smaller than 3. But this now implies that the arboricity is smaller or equal than 3 because of the minimality assumption. So, yes, this argument essentially uses ideas of Nash-Williams but it is not a direct consequence of Nash-Williams.