In extremal graph theory, the Erdős-Sós theorem, formerly known as the Erdős-Sós conjecture, is a theorem concerning the existence of trees as subgraphs of graphs with a sufficiently large average degree. It was first conjectured by Paul Erdős and Vera T. Sós in 1962 and remained an open problem for more than six decades before being proved in 2026.
Specifically, the theorem states that, for , every graph with average degree greater than contains every tree on vertices as a subgraph.
Note that the bound on the degree is tight, since the complete graph , that has an average degree of precisely does not contain any tree on vertices.
History The theorem appeared as a conjecture by Hungarian mathematicians Paul Erdős and Vera T. Sós in 1966, but it had been proposed earlier in 1962.
Before that, in 1959, it had been shown that the theorem holds if trees are replaced by paths. Other simplifications in the underlying trees include one-leg caterpillars trees of diameter 4 and spiders (rooted trees in which each vertex has degree one or two, except for the root). Other attempts at proving the conjecture proposed assumptions on the host graph, such as graphs of girth 5 or graphs not conatining the cycle .
In the 90's, Hungarian mathematicians Miklós Ajtai, János Komlós, Miklós Simonovits and Endre Szemerédi announced a proof of the conjecture for a sufficiently large . Their result, which relied on the Szemerédi regularity lemma, was supposed to appear in three different papers, that were never published.
In 2026, David Wood published a preprint presenting a proof of the Erdős–Sós conjecture in its original form. The proof was discovered by OpenAI's GPT-6 Astra large language model and subsequently presented by Wood in a mathematical exposition.
Related results A directed analogue of the Erdős–Sós theorem was studied by Santos, Stein, and Williams. The analogue concerns antidirected trees, that is, directed trees in which every vertex is either a source or a sink. It conjectures that every digraph on vertices with more than arcs contains every antidirected tree with arcs.
References