In a recent preprint (Delcourt and Postle 2026), Delcourt and Postle proved the celebrated Nash-Williams triangle decomposition conjecture, a central open problem in extremal design theory. Their result confirms that there is a constant such that every graph on vertices whose number of edges is divisible by , whose vertex degrees are all even, and whose minimum degree is at least , admits a decomposition of its edge set into edge-disjoint triangles.
We say that a graph is decomposed into subgraphs and , and write if is the edge-disjoint, though not necessarily vertex-disjoint, union of and . More generally, is -decomposable if where each is isomorphic to . The theory of graph decompositions asks under what conditions a graph admits such a decomposition.
An obvious necessary condition for -decomposability is -divisibility. We say that a graph is -divisible if divides and if the greatest common divisor of the degrees of the vertices of , denoted by , divides the degree of every vertex of . A central question in graph decomposition theory is when this necessary condition is also sufficient.
In a previous blog post, we discussed a theorem of Šajna (Šajna 2002), which states that if is a cycle of length and the complete graph is -divisible, then is -decomposable. A far-reaching generalization of this theme concerns decompositions of non-complete graphs of large minimum degree into cycles of a fixed length. This is an active direction of research.
For each , the cycle decomposition threshold is defined as the infimum of all such that every sufficiently large graph on vertices with minimum degree at least has a decomposition into cycles of length if and only if divides and every vertex of has even degree. In 2016, Barber, Kühn, Lo, and Osthus (Barber et al. 2016) reduced the problem in general to its natural fractional analogue. Using this reduction, they proved that For odd , the best known bounds are see (Bryant et al. 2024).
The most famous case is . Nash-Williams (Nash-Williams 1970) observed that and conjectured that equality holds. In other words, he conjectured that the obvious divisibility conditions for triangle decompositions become sufficient once the minimum degree is at least , for all sufficiently large graphs. In 2021, Delcourt and Postle (Delcourt and Postle 2021) proved the upper bound In 2026, they posted a preprint (Delcourt and Postle 2026) proving the Nash-Williams conjecture in full.
The authors first resolved the fractional version of the problem for . Together with earlier work (Glock et al. 2019), this implies the first statement of Theorem . The “moreover” part, which gives the exact threshold for triangle decompositions, required substantially more work.
There is an analogous threshold problem for clique decompositions. Let denote the infimum of all such that every sufficiently large graph on vertices with minimum degree at least has a decomposition into copies of if and only if the necessary divisibility conditions hold; namely, By definition, , and so Theorem proves that A folklore generalization predicted that However, this was disproved in (Delcourt et al. 2025), where it was shown that, for some constant and all ,