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$
  • $\begingroup$ Hi Akash, how did you arrive at this problem? $\endgroup$ – Ryan Williams Sep 12 '10 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$ – Robin Kothari Sep 12 '10 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$ – Akash Kumar Sep 12 '10 at 1:57
  • $\begingroup$ Akash, thank you for your honesty :) It certainly sounded like a homework problem. $\endgroup$ – Ryan Williams Sep 12 '10 at 3:02
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$
  • $\begingroup$ Gosh...I really feel dumb now. Anyway gphilip, thanks for your solution $\endgroup$ – Akash Kumar Sep 12 '10 at 4:35

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.