Deleted:Nash-Williams theorem

From WikiAlpha
Jump to: navigation, search
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 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)</math> where <math>V_i \neq \emptyset</math> there are at least t(k&nbsp;−&nbsp;1) crossing edges (Tutte 1961, Nash-Williams 1961).[1]
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 <math>U \subset V(G)</math>, the induced subgraph G[U] has size <math>|G[U]| \leq t(|U|-1)</math>.
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 =&nbsp;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


  1. 1.0 1.1 Diestel, Reinhard, 1959– Verfasser.. Graph theory. ISBN 9783662536216. OCLC 1048203362. 
  2. 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.