DIMACS TR: 2001-38

On a Conjecture of Loebl



Authors: Yi Zhao

ABSTRACT

Martin Loebl conjectured that if in a graph $G$ on $n$ vertices at least half the vertices have degree at least $n/2$, then $G$ contains, as subgraphs, all trees with at most $n/2$ edges. We prove the conjecture for sufficient large $n$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-38.ps.gz
DIMACS Home Page