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

Abstract

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 determine the extremal graphs for the Erd\H os--Sós Conjecture, and prove a related conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé, again determining the extremal graphs.