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.
