Nash-Williams theorem


In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees a graph can have:
A graph G has t edge-disjoint spanning trees iff for every partition where there are at least t crossing edges.
For this article, we will say that such a graph has arboricity t or is t-arboric.

Related tree-packing properties

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-aboric.
Both NW and Menger's theorem characterize when a graph has k edge-disjoint paths between two vertices.

Nash-Williams theorem for forests

NW generalized the above result to forests:
G can be partitioned into t edge-disjoint forests iff for every, the induced subgraph G has size.
A proof is given here.
This is how people usually define what it means for a graph to be t-aboric.
In other words, for every subgraph S = G, we have. It is tight in that there is a subgraph S that saturates the inequality. This leads to the following formula
also referred to as the NW formula.
The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.