Decomposing a Graph into Forests: The Nine Dragon Tree Conjecture is True

Abstract

The fractional arboricity of a graph G, denoted by Γ_f (G), is defined as

$${\Gamma _f}\left( G \right) = {\max _{H \subseteq G,v\left( H \right) > 1}}\frac{{e\left( H \right)}}{{v\left( H \right) - 1}}$$

. The celebrated Nash-Williams’ Theorem states that a graph G can be partitioned into at most k forests if and only if Γ_f (G)≤k. The Nine Dragon Tree (NDT) Conjecture [posed by Montassier, Ossona de Mendez, Raspaud, and Zhu, in “Decomposing a graph into forests”, J. Combin. Theory Ser. B 102 (2012) 38-52] asserts that if

$${\Gamma _f}\left( G \right) \leqslant k + \frac{d}{{k + d + 1}}$$

, then G decomposes into k+1 forests with one having maximum degree at most d. In this paper, we prove the Nine Dragon Tree (NDT) Conjecture.