A short proof of the Erd\H os–Sós Conjecture
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.
