Problem #580: Let $G$ be a graph on $n$ vertices such that at least $n/2$...

---

Progress

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$).

Zhao [Zh11] has proved this conjecture holds for all sufficiently large $n$.

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.