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

Long-Tu Yuan, Xiao-Dong Zhang

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


Keywords


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

Full Text:

PDF ABSTRACTS (EN/SI)


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