On the Erdos-Sos Conjecture for Graphs on n=k+4 Vertices

2014/03/21 by Long-Tu Yuan, Long‐Tu Yuan, Xiao-Dong Zhang +3
Computer Science · Mathematics · #05C05 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C05

paper · pdf · doi:10.48550/arxiv.1403.5430

18 pages

arxiv created 2014/03/21 · openalex publication_date 2014/03/21 · arxiv updated 2014/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Erdős-Sós Conjecture states that if G is a simple graph of order n with average degree more than k-2, then G contains every tree of order k. In this paper, we prove that Erdős-Sós Conjecture is true for n=k+4.

Related

• A local approach to the Erdős-Sós conjecture
• Embedding Nearly Spanning Trees
• An extension of a result concerning convex geometric graphs
• A Variation of the Erdős-Sós Conjecture in Bipartite Graphs
• The Erdös-Sós Conjecture for Spiders