2024/05/24 by Reed, Bruce, Stein, Maya
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.15733
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 δ>0 and k0∈\mathbb N such that the conjecture holds for every tree T with k ≥ k0 edges and every graph G with |V(G)| ≤ (1+δ)|V(T)|.