The Erdős-Sós conjecture, from 1963, states that any graph with average degree greater than k-2 contains every tree with k edges as a subgraph. For over sixty years, the conjecture has been proved only in special cases — bounded-degree trees, specific graph families, approximate versions with extra room in the degree condition.
Davoodi, Piguet, Řada, and Sanhueza-Matamala (arXiv:2603.17755) prove the conjecture asymptotically for dense host graphs, with no bounded-degree restriction on the guest trees. As k grows, the average degree threshold approaches k-2, and every tree with k edges can be found as a subgraph.
The removal of the bounded-degree restriction is the advance. Previous asymptotic results required that the tree being embedded had maximum degree bounded by some function — the tree couldn't have vertices with too many neighbors. This restriction was not part of the original conjecture but was imposed by the proof techniques. The new approach handles trees of arbitrary shape, including stars, caterpillars, and other high-degree structures that previous methods excluded.
The proof works for dense host graphs — those with a positive fraction of all possible edges. Sparse graphs remain open. Recent complementary work by Pokrovsky extends some results to sparse settings, but the full conjecture for both sparse hosts and unbounded-degree trees remains unresolved.
The conjecture captures a clean extremal principle: enough average degree forces the presence of every possible tree. The degree threshold is tight — there exist graphs with average degree exactly k-2 that miss certain k-edge trees. The asymptotic resolution confirms that the principle holds in the limit, even for the most pathological tree shapes, as long as the host graph is dense enough.