TOPICS

# Arboricity

Given a graph , the arboricity is the minimum number of edge-disjoint acyclic subgraphs (i.e., spanning forests) whose union is .

An acyclic graph therefore has .

It appears that a regular graph of vertex degree has arboricity

 (1)

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

 (2)

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

The arboricity of a planar graph is at most 3 (Harary 1994, p. 124, Problem 11.22).

The arboricity of the complete graph is given by

 (3)

and of the complete bipartite graph by

 (4)

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

Anarboricity, Spanning Tree

## Explore with Wolfram|Alpha

More things to try:

## References

Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.Harary, F. "Arboricity." In Graph Theory. Reading, MA: Addison-Wesley, pp. 90-92, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Nash-Williams, C. St. J. A. "Edge-Disjoint Spanning Trees of Finite Graphs." J. London Math. Soc. 36, 455-450, 1961.

Arboricity

## Cite this as:

Weisstein, Eric W. "Arboricity." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Arboricity.html