On the Erdős-Sós Conjecture and Double-brooms

Abstract

Let $G$ be a graph with average degree greater than $k–2$. Erdős and Sós conjectured that $G$ contains every tree on $k$ vertices. A star is a tree consisting of one center vertex adjacent to all the other vertices, and a $double-broom$ is a tree made up of two stars and a path connecting the center of one star with the center of the other. If the path connecting the two stars has length 2 or 3, then $G$ contains the double-broom (unpublished). In this paper, we prove that $G$ contains every double-broom on $k$ vertices.