Embedding Nearly Spanning Trees

Abstract

The Erdős-Sós Conjecture states that every graph with average degree exceeding $k-1$ contains every tree with $k$ edges as a subgraph. We prove that there are $\hat{I}´>0$ and $k_0\in \mathbb{N}$ such that the conjecture holds for every tree $T$ with $k\ge k_0$ edges and every graph $G$ with $|V(G)|\le (1+\hat{I}´)|V(T)|$.