# Arboricity

From Egres Open

Let *G=(V,E)* be an undirected graph. For a node set [math]X \subseteq V[/math], [math]i_G(X)[/math] denotes the number of induced edges in *X*. The **arboricity** of *G* is

[math]\mbox{arb}(G)=\max_{X \subseteq V, |X| \geq 2} \frac{i_G(X)}{|X|-1}.[/math]

Sometimes this is referred to as the "fractional arboricity" of *G*. Nash-Williams' forest cover theorem states that *G* can be covered by *k* forests if and only if its arboricity is at most *k*.