I have a graph theory proof that I have been advised to do by induction but I am having a bit of trouble completing the induction step.
The question is:
Let T be a tree on k vetices. Prove that if G is a graph where every vertex has degree at least k-1, then T is isomorphic to some subgraph of G.
So far I have:
1) Check that n=1 works. If n=1 then all the trees are vertices, which are going to be isomorphic to some subgraph of G.
2) Assume n=k holds. This means that we have a tree on k vertices that is isomorphic to some subgraph of G, where G is a graph where every vertex has degree at least k-1.
3) Now see if the n=k+1 case holds.
Now we have a tree on k+1 vertices and a graph where every vertex has degree at least k…
How do I actually show that the induction step (3) holds?
Best Answer
You know that in your graph $G$ with each vertex of degree at least $k$ there exists a subgraph isomorphic to the tree $T_{k}$. All we need now is one more vertex in $G$ to tack onto $T_k$ which isn't already contained in $T_k$.
Examine the vertices adjacent to some end-point $t$ of the tree $T_k$. How do we know that there must be a vertex adjacent to $t$ not contained in $T_k$?