On the Erdős-Sós Conjecture for graphs on n = k + 4 vertices

Long-Tu Yuan, Xiao-Dong Zhang


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 Erds-Sós Conjecture is true for n = k + 4.


Erdős-Sós Conjecture, Conjecture, tree, maximum degree

Full Text:


DOI: https://doi.org/10.26493/1855-3974.905.cb4

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications