# Rooted trees on simple graphs

I came across this problem and I'm really struggling with it. Let $G$ be a simple graph with minimum degree $k$. Then $G$ contains a copy of every rooted tree of $k+1$ vertices.

I lack good intuition in most graph problems, so I tried induction on $k$, on the number of vertices and on the number of edges. For example, when trying to apply induction on $k$ I don't know how to justify that I can delete edges until the graph has minimum degree $k-1$.

I can't find a general argument without doing complicated cases or being too informal.

Any help would be much appreciated!

• What does the root have to do with it? How is embedding a rooted tree in a graph $G$ different from embedding a plain tree in $G$? Do you have to do something special with the root? – bof Jan 7 '14 at 21:34
• No, this question was part of an exam took a while ago and looking on a book (Bondy's Graph Theory) I came up with it, it was missing something: "Show that any simple graph with minimum degree k contains a copy of each rooted tree on k + 1 vertices, rooted at any given vertex of the graph." Thanks a lot! Your answer solves a lot of trouble because I had a hard time knowing how to apply the induction hypotheses... – Serge Jan 8 '14 at 2:29

I'm not sure what the root has to do with it, but here's how I'd do it for plain (unrooted) trees. The statement I'd prove by induction on $k$ is "a simple graph with minimum degree at least $k$ contains a copy of every tree with $k+1$ vertices." To do the induction step (from $k$ to $k+1$): let $G$ be a simple graph with minimum degree at least $k+1$, and let $T$ be a tree with $k+2$ vertices. Let $v$ be a leaf of $T$, and let $u$ be its neighbor. By the induction hypotheses, $G$ contains a copy $T_0'$ of the tree $T_0=T-v$. Let $u'$ be the vertex of $T_0'$ corresponding to the vertex $u$ of $T_0$. Since $u'$ has at least $k+1$ neighbors in $G$, it has a neighbor $v'$ which is not a vertex of $T_0'$. Adding the vertex $v'$ and the edge $u'v'$ to $T_0'$, we get a copy of $T$ in $G$.