# Deleted:Nash-Williams theorem

From WikiAlpha

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 graphFor this article, we will say that such a graph hasGhastedge-disjoint spanning trees iff for every partition <math display="inline">V_1, \ldots, V_k \subset V(G)</math> where <math>V_i \neq \emptyset</math> there are at leastt(k − 1) crossing edges (Tutte 1961, Nash-Williams 1961).^{[1]}

**arboricity **or is

*t**t*-

**arboric**. (The actual definition of arboricity is slightly different and applies to forests rather than trees.)

## Contents

## Related tree-packing properties

A *k*-arboric graph is necessarily *k*-edge connected. The converse is not true.

As a corollary of NW, every 2*k*-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 intoA proof is given here.tedge-disjoint forests iff for every <math>U \subset V(G)</math>, the induced subgraphG[U] has size <math>|G[U]| \leq t(|U|-1)</math>.

^{[2]}

^{[1]}

This is how people usually define what it means for a graph to be *t*-aboric.

*S*=

*G*[

*U*], we have <math>t \geq E(S) / (V(S) - 1)</math>. 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

<math>t = \max_{S \subset G} \frac{E(S)}{V(S) - 1}</math>also referred to as the

**NW formula.**

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

## See also

- Arboricity
- Bridge (cut edge)
- Menger's theorem
- Tree packing conjecture

## References

- ↑
^{1.0}^{1.1}Diestel, Reinhard, 1959– Verfasser..*Graph theory*. ISBN 9783662536216. OCLC 1048203362. http://worldcat.org/oclc/1048203362. - ↑ Chen, Boliong; Matsumoto, Makoto; Wang, Jianfang; Zhang, Zhongfu; Zhang, Jianxun (1994-03-01). "A short proof of Nash-Williams' theorem for the arboricity of a graph" (in en).
*Graphs and Combinatorics***10**(1): 27–28. doi:10.1007/BF01202467. ISSN 1435-5914. https://doi.org/10.1007/BF01202467.