0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bof Jan 7 '14 at 21:34
  • $\begingroup$ 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... $\endgroup$ – Serge Jan 8 '14 at 2:29
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.