7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Hi Akash, how did you arrive at this problem? $\endgroup$ Commented Sep 12, 2010 at 1:47
  • $\begingroup$ 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. $\endgroup$ Commented Sep 12, 2010 at 1:51
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Sep 12, 2010 at 1:57
  • $\begingroup$ Akash, thank you for your honesty :) It certainly sounded like a homework problem. $\endgroup$ Commented Sep 12, 2010 at 3:02

1 Answer 1

14
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Gosh...I really feel dumb now. Anyway gphilip, thanks for your solution $\endgroup$ Commented Sep 12, 2010 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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