# Deleted:Nash-Williams theorem

 The below content is licensed according to Creative Commons Attribution-ShareAlike License contrary to the public domain logo at the foot of the page. It originally appeared on http://en.wikipedia.org. The original article might still be accessible here. You may be able to find a list of the article's previous contributors on the talk page.

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 <math display="inline">V_1, \ldots, V_k \subset V(G)[/itex] where $V_i \neq \emptyset$ there are at least t(k&nbsp;−&nbsp;1) crossing edges (Tutte 1961, Nash-Williams 1961).
For this article, we will say that such a graph has arboricity&nbsp;t or is t-arboric. (The actual definition of arboricity is slightly different and applies to forests rather than trees.)

## 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 (1964) generalized the above result to forests:
G can be partitioned into t edge-disjoint forests iff for every $U \subset V(G)$, the induced subgraph G[U] has size $|G[U]| \leq t(|U|-1)$.
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 =&nbsp;G[U], we have $t \geq E(S) / (V(S) - 1)$. It is tight in that there is a subgraph S that saturates the inequality (or else we can choose a smaller t). This leads to the following formula
$t = \max_{S \subset G} \frac{E(S)}{V(S) - 1}$
also referred to as the NW formula.

The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.