The Erdös-Sós Conjecture for Spiders

Genghua Fan, Yanmei Hong, Qinghai Liu

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 d…