Arboricity

Given a graph , the arboricity is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose graph union is . Nash-Williams (1961) showed this is equivalent to

			(1)
			(2)

where is the edge count of a subgraph , is the vertex count of a subgraph, and is the maximum average degree over all subgraphs.

For any graph,

(3)

where is the vertex count and is the edge count (Nash-Williams 1961).

This bound immediately gives a number of useful lower bounds. If is the graph degeneracy of , then , so

(4)

This bound is often very quick to evaluate, although it need not be sharp. A stronger lower bound is obtained by repeatedly deleting a vertex of minimum degree and considering the resulting chain of residual subgraphs

(5)

Then

(6)

is also a lower bound for the arboricity, since each is a subgraph of . This peeling bound is always at least as large as , but it is not exact in general, because a densest witness subgraph need not occur along a single minimum-degree peeling chain. For example, the bishop graph on a board has peeling bound 3 but arboricity 4, the bishop graph on an board has peeling bound 5 but arboricity 6, and the camel graph on a board has peeling bound 2 but arboricity 3.

An acyclic graph therefore has . Furthermore, the arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22).

Let be a nonempty graph on vertices and edges and let be the maximum number of edges in any subgraph of having vertices. Then

(7)

(Nash-Williams 1961; Harary 1994, p. 90).

The arboricity of the complete graph is given by

(8)

of the complete bipartite graph by

(9)

(Harary 1994, p. 91), where is the ceiling function, and of the complete tripartite graph by

(10)

In general, the arboricity of the complete multipartite graph is

(11)

Equivalently, if

(12)

is the number of vertices, then

(13)