The Erdös-Sós Conjecture for Spiders

Abstract

The Erdös-Sós conjecture states that if $G$ is a graph with average degree more than $k-1$, then G contains every tree of $k$ edges. A spider is a tree with at most one vertex of degree more than 2. In this paper, we prove that Erdös-Sós conjecture holds for all spiders.

17 pages