## 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