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

An acyclic graph therefore has Upsilon(G)=1.

It appears that a regular graph G of vertex degree d has arboricity


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


(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 K_n is given by


and of the complete bipartite graph K_(m,n) by


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

See also

Anarboricity, Spanning Tree

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "Arboricity." From MathWorld--A Wolfram Web Resource.

Subject classifications