← All papers
First page of A short proof of the Erd\H os–Sós Conjecture

A short proof of the Erd\H os–Sós Conjecture

Oliver Riordan, Alex Scott

math.CO Sep 14, 2026 · v3
Cites a third-party Lean 4 verification (GitHub repository) of the Erdős–Sós conjecture proof that the note simplifies; the authors' own arguments are not formalized.
The Erd\H os–Sós Conjecture was recently proved by GPT-6 Astra, using a very ingenious and surprising argument. In this note, we present a simplified version of this argument in an (arguably) more natural form. We also prove a related conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, and give a substantially simplified proof of an analogous result for eulerian digraphs, again proved by GPT-6 Astra, and announced by Mubayi and Verstraete. In addition, we determine the extremal (di)graphs for all three problems.

The Erdős–Sós conjecture states that a graph with average degree above k−2 contains every tree on k vertices. It was recently proved by GPT-6 Astra, and a Lean 4 verification of that proof exists. The note seeks a simpler, more natural presentation and treats related problems.

For a rooted tree T and a random vertex ordering, an edge from the first vertex is called T-jumping if a rooted copy of T appears among earlier vertices. Induction on |T| shows the expected number of T-jumping edges is at least d−|T|+1. Removing a leaf from T then gives the conjecture. The same argument extends to antidirected trees in digraphs, and further analysis characterizes the extremal graphs and digraphs.

The note gives a short proof of the Erdős–Sós conjecture and proves the Addario-Berry–Havet–Linhares Sales–Reed–Thomassé conjecture for antidirected trees. It gives a simplified proof for eulerian digraphs and determines the extremal (di)graphs for all three problems. The Lean verification it cites is a third-party repository for GPT-6 Astra's original proof.