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 \( {\textstyle V_{1},\ldots ,V_{k}\subset V(G)} \) where \( {\displaystyle V_{i}\neq \emptyset } \) there are at least t(k − 1) crossing edges (Tutte 1961, Nash-Williams 1961).[1]

For 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.)

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 \( {\displaystyle U\subset V(G)} \) , the induced subgraph G[U] has size \({\displaystyle |G[U]|\leq t(|U|-1)}. \)

A proof is given here.[2][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 \( {\displaystyle t\geq \lceil E(S)/(V(S)-1)\rceil } \) . 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

\( {\displaystyle t=\lceil \max _{S\subset G}{\frac {E(S)}{V(S)-1}}\rceil } \)

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

Diestel, Reinhard, 1959– Verfasser. (2017-06-30). Graph theory. ISBN 9783662536216. 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". Graphs and Combinatorics. 10 (1): 27–28. doi:10.1007/BF01202467. ISSN 1435-5914.

Undergraduate Texts in Mathematics

Graduate Studies in Mathematics

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"

All text is available under the terms of the GNU Free Documentation License