On the Erdős-Sós Conjecture and Graphs with Large Minimum Degree

Abstract

Suppose \(G\) is a simple graph with average vertex degree greater than \(k – 2\). Erdős and Sós conjectured that \(G\) contains every tree on \(k\) vertices. Sidorenko proved \(G\) contains every tree that has a vertex \(v\) with at least \(\left\lfloor\frac{k}{2}\right\rfloor – 1\) leaf neighbors. We prove this is true if \(v\) has only \(\left\lceil\frac{k}{2}\right\rceil – 2\) leaf neighbors. We generalize Sidorenko’s result by proving that if \(G\) has minimum degree \(d\), then \(G\) contains every tree that has a vertex with at least \((k – 1) – d\) leaf neighbors. We use these results to prove that if \(G\) has average degree greater than \(k – 2\) and minimum degree at least \(k – 4\), then \(G\) contains every tree on \(k\) vertices.