Nash-Williams theorem for forests
Statement
In 1964, Nash-Williams 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.
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.
Further reading
- Wikipedia, page 60654680, revision 1332584259, Nash-Williams theorem, section Nash-Williams theorem for forests. adopted
About this page
| Tag | 4FN0MDVK8E |
|---|---|
| URI | m2://4FN0MDVK8E |
| Kind | statement, theorem |
| Writing | W0 stub |
| Status | This copy of the site has no build data. Run m2 status 4FN0MDVK8E. |
| Changed | 4 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.