On the Erdős-Sós Conjecture for Graphs on $n=k+3$ Vertices

Abstract

Erdős and Sós conjectured in $1962$ that if the average degree of a graph $G$ exceeds $k–2$, then $G$ contains every tree on $k$ vertices. Results from Sauer and Spencer (and independent results from Zhou) prove the special case where $G$ has $k$ vertices. Results from Slater, Teo, and Yap prove the case where $G$ has $k+1$ vertices. In $1996$, Woźniak proved the case where $G$ has $k+2$ vertices. We prove the conjecture for the case where $G$ has $k+3$ vertices.