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).

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

(4)

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

The arboricity of the complete graph is given by

(5)

and of the complete bipartite graph by

(6)

(Harary 1994, p. 91), where is the ceiling function.