Top Qs
Timeline
Chat
Perspective

Nash-Williams theorem

Theorem in graph theory describing number of edge-disjoint spanning trees a graph can have From Wikipedia, the free encyclopedia

Remove ads

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

Remove ads

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

Summarize
Perspective

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

A graph can be partitioned into edge-disjoint forests iff for every , the induced subgraph has at most 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 , we have . It is tight in that there is a subgraph that saturates the inequality (or else we can choose a smaller ). This leads to the following formula

,

also referred to as the Nash-Williams formula.

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

Remove ads

See also

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads