Basic arboricity example

Question

I'm having some trouble proving two interesting properties of arboricity of a graph. Arboricity is defined as the minimal number of forests into which a graph can be divided, and it can also be expressed by a formula via the Nasch-Williams theorem. However, I'd like to strictly restrict to the definition without using the Nash-Williams theorem.

My first goal is to prove an $n$-vertex complete graph $G$ has an arboricity of $\frac{n}{2}$ (ofcourse without using Nash-Williams). I tried the following: I know each forest can hold up to $n-1$ edges. The total amount of edges in $G$ is $\frac{n\cdot\left( n -1 \right)}{2}$. Hence the arboricity of $G$ cannot be lower then $\frac{n}{2}$.

But how do I prove it cannot be larger?

A different approach to this that I have tried is without searching for upper and lower bound, but simply finding such a decomposition. I tried to find a general way to construct such a forest decomposition, but could not find.

Similarly to this, I am also attempting to prove a planar graph has arboricoty $\leq 3$, but I find it even harder then for the complete graph.

Answer 1

Here is an inductive construction:

Assume you have a decomposition in $n-1$ trees for $K_{2n-2}$. We can build a decomposition of $K_{2n}$ in $n$ trees in the following way: for $i = 1 \ldots n-1$, in the $i-th$ tree:

• The edges between $v_1, \ldots v_{2n-2}$ in the $i$-th tree are the same as in the $K_{2n-2}$ construction.

• $v_{2n-1}$ is connected to $v_{i}$

• $v_{2n}$ is connected to $v_{n-1+i}$

Then let the $n$-th tree be the one formed by connecting $v_{2n-1}$ with $v_n, \ldots v_{2n-2}$, $v_{2n}$ with $v_1, \ldots v_{n-1}$ and connecting $v_{2n-1}$ and $v_{2n}$ together.

Answer 2

In fact, you can partition $K_{2n}$ into $n$ paths of length $2n-1$ as follows. Number the vertices $1$ to $2n$. For each $i=1,2,\dots,n$, the $i^{th}$ path is $$ (i,i+1,i-1,i+2,i-2,i+3,i-3,\dots,i+n-1,i-n+1,i+n) $$ All addition is modulo $2n$. Each path is a zig zag. When $n=4$, the result is

To partition $K_{2n+1}$ into $n+1$ trees, perform this construction on the vertices number $1$ through $2n$, then add one more tree consisting of vertex number $2n+1$ connected to every other vertex.