OPEN

Let $G$ be a graph on $n$ vertices such that at least $n/2$ vertices have degree at least $n/2$. Must $G$ contain every tree on at most $n/2$ vertices?

A conjecture of Erdős, Füredi, Loebl, and Sós. Ajtai, Komlós, and Szemerédi [AKS95] proved an asymptotic version, where at least $(1+\epsilon)n/2$ vertices have degree at least $(1+\epsilon)n/2$ (and $n$ is sufficiently large depending on $\epsilon$).

Komlós and Sós conjectured the generalisation that if at least $n/2$ vertices have degree at least $k$ then $G$ contains any tree with $k$ vertices.