In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:
A graph G has t edge-disjoint spanning trees iff for every partition whereFor this article, we will say that such a graph has arboricity t or is t-arboric. (The actual definition of arboricity is slightly different and applies to forests rather than trees.)there are at least t(k − 1) crossing edges (Tutte 1961, Nash-Williams 1961).[1] [2]Vi ≠ \emptyset
A k-arboric graph is necessarily k-edge connected. The converse is not true.
As a corollary of NW, every 2k-edge connected graph is k-arboric.
Both NW and Menger's theorem characterize when a graph has k edge-disjoint paths between two vertices.
In 1964, Nash-Williams[3] generalized the above result to forests:
G can be partitioned into t edge-disjoint forests iff for everyA proof is given here.[4], the induced subgraph G[''U''] has at mostU\subsetV(G)
edges.t(|U|-1)
This is how people usually define what it means for a graph to be t-aboric.
In other words, for every subgraph S = G[''U''], we have
t\geq\lceilE(S)/(V(S)-1)\rceil
also referred to as the NW formula.t=\lceilmaxS
E(S) V(S)-1 \rceil
The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.