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

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

CC BY-SA 2.5
2010-09-12T04:35:50.947Z
Gosh...I really feel dumb now. Anyway gphilip, thanks for your solution
Akash Kumar
CC BY-SA 2.5
2010-09-12T02:55:02.177Z
2010-09-12T02:55:02.177Z
gphilip
<p>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.</p>

<p>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 :(</p>

<p>Sorry, if the question is too dumb.
)</p>

CC BY-SA 2.5
2010-09-12T01:47:50.810Z
Hi Akash, how did you arrive at this problem?
Ryan Williams
CC BY-SA 2.5
2010-09-12T01:51:10.930Z
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
CC BY-SA 2.5
2010-09-12T01:57:50.320Z
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. http://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
CC BY-SA 2.5
2010-09-12T03:02:12.120Z
Akash, thank you for your honesty :) It certainly sounded like a homework problem.
Ryan Williams
<graph-theory><co.combinatorics>
Graph Theory Fun Problem
Akash Kumar
# Graph Theory Fun Problem

(Asked by: username_0 on 2010-09-12)

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

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: Hi Akash, how did you arrive at this problem?  
> **username_2**: 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.  
> **username_0**: 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. http://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  
> **username_1**: Akash, thank you for your honesty :) It certainly sounded like a homework problem.  

---

## 1 answers

### Answer by username_3 on 2010-09-12. Score: 14 | Accepted answer

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

> **Comments:**
> **username_0**: Gosh...I really feel dumb now. Anyway username_3, thanks for your solution  

---

