Abstract

A well-known conjecture of Erdos and Sos states that every graph with average degree exceeding m-1 contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least [2m/3] contains every tree with m edges. As evidence for our conjecture we show (a) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (b) there is a gamma > 0 such that the weakening of the conjecture obtained by replacing [2m/3] by (1-gamma)m holds.