Constructing trees in graphs with no K 2, s

Let s  ≥ 2 be an integer and k  > 12( s  − 1) an integer. We give a necessary and sufficient condition for a graph G containing no K 2, s with $\delta(G)\ge{k}/2$ and $\Delta(G)\ge k$ to contain every tree T of order k  + 1. We then show that every graph G with no K 2, s and average degree greater than k  − 1 satisfies this condition, improving a result of Haxell, and verifying a special case of the Erdős—Sós conjecture, which states that every graph of average degree greater than k  − 1 contains every tree of order k  + 1. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 301–310, 2007