The extremal cases of the Erd\H os--Sós conjecture

Abstract

The Erd\H os--Sós conjecture states that every $n$-vertex graph $G$ with more than $(k-2)n/2$ edges contains every $k$-vertex tree. We solve the extremal cases of this conjecture, showing that for some fixed $\mu >0$, the conjecture holds for each $G$ that minimally satisfies the assumptions of the conjecture and has a subgraph~$H$ of minimum degree $\delta (H)\ge (1-\mu )k$. In our proof, we mainly have to deal with $H$ taking two different shapes: either $H$ is close to the complete graph $K_k$ or $H$ is close to the complete bipartite graph $K_{k,k}$.

Minimal changes to the first version, mainly just added a paragraph acknowledging the recent AI proof