Nash-Williams theorem

{{short description|Theorem in graph theory describing number of edge-disjoint spanning trees a graph can have}}

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 $V_1, \ldots, V_k \subset V(G)$ where $V_i \neq \emptyset$ there are at least t(k − 1) crossing edges.

The theorem was proved independently by Tutte{{cite journal |last1=Tutte |first1=W. T. |title=On the problem of decomposing a graph into $n$ connected factors|journal=Journal of the London Mathematical Society |date=1961 |volume=36 |issue=1 |pages=221-230 |doi=10.1112/jlms/s1-36.1.221}} and Nash-Williams,{{cite journal |last1=Nash-Williams |first1=Crispin St. John Alvah |title=Edge-Disjoint Spanning Trees of Finite Graphs |journal=Journal of the London Mathematical Society |date=1961 |volume=36 |issue=1 |pages=445–450 |doi=10.1112/jlms/s1-36.1.445}} both in 1961. In 2012, Kaiser{{cite journal |last1=Kaiser |first1=Tomáš |title=A short proof of the tree-packing theorem |journal=Discrete Mathematics |date=2012 |volume=312 |issue=10 |pages=1689-1691 |doi=10.1016/j.disc.2012.01.020 |arxiv=0911.2809}} 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{{cite journal |last1=Nash-Williams |first1=Crispin St. John Alvah |title=Decomposition of Finite Graphs Into Forests |journal=Journal of the London Mathematical Society |date=1964 |volume=39 |issue=1 |page=12 |doi=10.1112/jlms/s1-39.1.12}} generalized the above result to forests:

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

Other proofs are given here.{{Cite journal|last1=Chen|first1=Boliong|last2=Matsumoto|first2=Makoto|last3=Wang|first3=Jianfang|last4=Zhang|first4=Zhongfu|last5=Zhang|first5=Jianxun|date=1994-03-01|title=A short proof of Nash-Williams' theorem for the arboricity of a graph|journal=Graphs and Combinatorics|language=en|volume=10|issue=1|pages=27–28|doi=10.1007/BF01202467|s2cid=206791653 |issn=1435-5914}}{{Cite book|title=Graph theory|last=Diestel|first= Reinhard|isbn=9783662536216|oclc=1048203362|date = 2017-06-30}}

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

In other words, for every subgraph $S=G[U]$ , we have $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

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

References

External links

Paulson, Lawrence C. [https://www.isa-afp.org/entries/Nash_Williams.html The Nash-Williams partition theorem (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)]

Category:Theorems in graph theory

Nash-Williams theorem

Related tree-packing properties

Nash-Williams theorem for forests

See also

References

External links