Nash-Williams theorem

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.

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

Related tree-packing properties

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.

Nash-Williams theorem for forests

In 1964, Nash-Williams ^[4] generalized the above result to forests:

A graph ${\displaystyle G}$ can be partitioned into ${\displaystyle t}$ edge-disjoint forests iff for every ${\displaystyle U\subset V(G)}$, the induced subgraph ${\displaystyle G[U]}$ has at most ${\displaystyle t(|U|-1)}$ edges.

Other proofs are given here. ^{[5] [6]}

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

In other words, for every subgraph ${\displaystyle S=G[U]}$, we have ${\displaystyle t\geq \lceil E(S)/(V(S)-1)\rceil }$. It is tight in that there is a subgraph ${\displaystyle S}$ that saturates the inequality (or else we can choose a smaller ${\displaystyle 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 Nash-Williams formula.

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

See also

• Arboricity
• Bridge (cut edge)
• Matroid partitioning
• Menger's theorem
• Tree packing conjecture

References

1. Tutte, W. T. (1961). "On the problem of decomposing a graph into ${\displaystyle n}$ connected factors". Journal of the London Mathematical Society. 36 (1): 221–230. doi:10.1112/jlms/s1-36.1.221.
2. Nash-Williams, Crispin St. John Alvah (1961). "Edge-Disjoint Spanning Trees of Finite Graphs". Journal of the London Mathematical Society. 36 (1): 445–450. doi:10.1112/jlms/s1-36.1.445.
3. Kaiser, Tomáš (2012). "A short proof of the tree-packing theorem". Discrete Mathematics. 312 (10): 1689–1691. arXiv: 0911.2809 . doi:10.1016/j.disc.2012.01.020.
4. Nash-Williams, Crispin St. John Alvah (1964). "Decomposition of Finite Graphs Into Forests". Journal of the London Mathematical Society. 39 (1): 12. doi:10.1112/jlms/s1-39.1.12.
5. 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. S2CID   206791653.
6. Diestel, Reinhard (2017-06-30). Graph theory. ISBN   9783662536216. OCLC   1048203362.

External links

• Paulson, Lawrence C. The Nash-Williams partition theorem (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)