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.