Abstract

We conjecture that every graph of minimum degree at least 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 result relies on a general embedding tool for embedding trees into graphs of certain structure. This tool also has implications for the Erdos-Sos conjecture and the 2/3-conjecture. We prove an approximate version of both conjectures for bounded degree trees and dense host graphs.