Math 2.0

Theorem

Nash-Williams theorem for forests

Statement

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

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

Other proofs are given here.

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]S=G[U], we have t≥⌈E(S)/(V(S)−1)⌉t \geq \lceil E(S) / (V(S) - 1) \rceil. It is tight in that there is a subgraph SS that saturates the inequality (or else we can choose a smaller tt). This leads to the following formula

t=⌈max⁡S⊂GE(S)V(S)−1⌉,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.

Further reading

  1. Wikipedia, page 60654680, revision 1332584259, Nash-Williams theorem, section Nash-Williams theorem for forests. adopted
About this page
Tag4FN0MDVK8E
URIm2://4FN0MDVK8E
Kindstatement, theorem
WritingW0 stub
StatusThis copy of the site has no build data. Run m2 status 4FN0MDVK8E.
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • edge uses out: each definition that the statement needs (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.