The anarboricity of a graph 
is the maximum number of edge-disjoint nonacyclic (i.e., cyclic) subgraphs of 
whose union is 
(Harary and Palmer 1973a, p. 225). It is the packing
version of the covering invariant arboricity (Harary
and Palmer 1973a, p. 225). For example, in the 
graph, a maximum of two edge-disjoint cycles cover
the graph as illustrated above, making its anarboricity 2.
The term "anarboricity" is a "glorious groaning pun" (in the words of Harary and Palmer 1973b, p. 268) on the city of Ann Arbor (the location of the main campus of the University of Michigan).
Anarboricity is defined only for cyclic graphs but may be assigned a value 0 for acyclic graphs. It equals 1 for a unicyclic graph (since the only cyclic subgraph from which the original graph can be constructed is the entire graph).
Bridges and leaves do not contribute to anarboricity since, given a valid decomposition of the cyclic core, bridges and leaf edges can be assigned to any one of the constituent cyclic subgraphs. As a result, the anarboricity of a general cyclic graph is equal to the anarboricity of its 2-edge-connected core. Moreover, the anarboricity of a graph is equal to the sum of anarboricities of its blocks.
The anarboricity satisfies
 |
(1)
|
for a graph 
with edge count 
since every nonacyclic subgraph contains at least one
cycle, the shortest possible cycle has 3 edges, and subgraphs must be edge-disjoint.
This bound is tight for odd complete graphs 
with 
. For even 
, choosing one cycle from each nonacyclic subgraph gives edge-disjoint
cycles whose union has even degree at every vertex, so at least 
edges of 
lie outside these chosen cycles. Therefore,
 |
(2)
|
The edge-count bound is also tight for any graph that admits a decomposition into edge-disjoint triangles, such as the triangular grid graph.
By construction, the Dutch windmill graph 
has anarboricity 
, and the special case of the butterfly
graph 
has anarboricity 2.
The wheel graph 
has anarboricity
 |
(3)
|
as can be seen from the illustrations above.
