Logo
All Random Solved Random Open
OPEN
Let $n\geq k+1$. Every graph on $n$ vertices with at least $n(k-1)/2+1$ edges contains every tree on $k+1$ vertices.
A problem of Erdős and Sós. It can be easily proved by induction that every graph on $n$ vertices with at least $n(k-1)+1$ edges contains every tree on $k+1$ vertices.

Brandt and Dobson [BrDo96] have proved this for graphs of girth at least $5$. Wang, Li, and Liu [WLL00] have proved this for graphs whose complements have girth at least $5$. Saclé and Woznik [SaWo97] have proved this for graphs which contain no cycles of length $4$. Yi and Li [YiLi04] have proved this for graphs whose complements contain no cycles of length $4$.

Implies [547] and [557].

See also the entry in the graphs problem collection.