Degree conditions for embedding trees

Abstract

We conjecture that every $n$-vertex graph of minimum degree at least $\frac{k}{2}$ and maximum degree at least $2k$ contains all trees with $k$ edges as subgraphs. We prove an approximate version of this conjecture for trees of bounded degree and dense host graphs. Our work also has implications on the Erd\H os--Sós conjecture and the $\frac{2}{3}$-conjecture. We prove an approximate version of both conjectures for bounded degree trees and dense host graphs.

54 pages