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
The theorem was proved independently by Tutte[1] and Nash-Williams,[2] both in 1961.
In 2012, Kaiser[3] gave a short elementary proof.
For this article, we 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.)
A k-arboric graph is necessarily k-edge connected.
The converse is not true.
As a corollary of the Nash-Williams theorem, every 2k-edge connected graph is k-arboric.
Both Nash-Williams' theorem and Menger's theorem characterize when a graph has k edge-disjoint paths between two vertices.
In 1964, Nash-Williams[4] generalized the above result to forests:A graph
edge-disjoint forests iff for every
[5][6] This is how people usually define what it means for a graph to be t-aboric.
that saturates the inequality (or else we can choose a smaller
,also referred to as the Nash-Williams formula.
The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.