{"id":"arxiv/2609.05411","url":"https://arxiv.org/abs/2609.05411","tags":["math.CO"],"score":0,"title":"The extremal cases of the Erd\\H os--Sós conjecture","domain":"math.CO","source":"arxiv","authors":["Bruce Reed","Maya Stein"],"reviews":0,"subject":"math.CO","summary":"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 $μ>0$, the conjecture holds for each $G$ that minimally satisfies the assumptions of the conjecture and has a subgraph~$H$ of minimum degree $δ(H)\\ge (1-μ)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}$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}