Trees in a graph

posted Jun 17 '12

Shiva Kintali
691 ● 1 ● 6 ● 22
http://www.cs.princeton.e...

Let $k \geq 1$ be an integer, and let $T$ be a tree on $k+1$ vertices. Show that if a graph $G$ has minimum degree at least $k$, then $G$ has a subgraph isomorphic to $T$.