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.
See also the entry in the graphs problem collection.
