# Graph Theory Fun Problem

Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices.

I have not been able to solve the question so far. However, I would like if someone can invoke the probabilistic method to prove the above statement (as in if someone can show that the probability of not finding some tree on $k+1$ vertices as some subgraph of $G$ is less than $1$. My earlier efforts aimed at trying to show that we can somehow show that this graph contains $K_{k+1}$ which was obviously false. Next, I tried showing that a sequence of edge contractions can give a $K_{k+1}$. Though I have not shown it so far, I was wondering what good that result might have been. So far, sadly, I have gotten nowhere :(

Sorry, if the question is too dumb. )

• Hi Akash, how did you arrive at this problem? – Ryan Williams Sep 12 '10 at 1:47
• I'm not sure about k or k+1, but I am aware of the result that any graph with k|V| edges contains as a subgraph any forest on k vertices. – Robin Kothari Sep 12 '10 at 1:51
• To be fair Ryan, I would rather not answer that as that would amount to embarassing myself. But anyways, here is the answer. It was a problem that was given in my course of graph theory in a set of problems supposed to be tried for ourselves. Its the first problem for week 2 at the following link. people.math.gatech.edu/~thomas/TEACH/6014. Oh yes, its not a homework and I think it might be okay to ask this problem here. In case its not, please let me know and I will delete it – Akash Kumar Sep 12 '10 at 1:57
• Akash, thank you for your honesty :) It certainly sounded like a homework problem. – Ryan Williams Sep 12 '10 at 3:02

Let $G$ be the host graph and $T$ the tree. Try "growing" $T$ in $G$. At each step, mark in $G$ the subtree $T'$ of $T$ that has been grown so far. Using the bounds on $\delta(G)$ and $\vert V(T)\vert$, argue that we can always expand the marked subgraph if it is not yet isomorphic to $T$.
Oh, but you wanted the Probabilistic Method. Here we go: Toss a coin $k$ times, throw out the results, and then do the above (old joke).