Let T be a tree with n vertices. G be a non-empty graph with $\delta$(G) $\ge$ n-1. Prove that T is a subgraph of G.
If it's a tree then I know it has to be connected and if the minimum degree is greater than or equal to n-1 vertices wouldn't it have to be the star graph? Not really sure where to go, tried drawing a couple pictures, but I always end up with a star graph?
Best Answer
You prove this by induction on the number of edges $m \in \mathbb{Z}^{+}$. If $m = 0, 1$, the result is obvious. At $m = 0$, $T$ is a single vertex. At $m = 1$, $T$ is a single edge, and $G$ is guaranteed to have an edge as $\delta(G) = 1$.
Now assume true up to an arbitrary $k > 1$, and we now prove true for the $k+1$ case. Let $T$ be a tree with $k+1$ edges. Let $T^{\prime} = T - \{v\}$, for some leaf $v$. Let $w$ be the neighbor of $v$ in $T$. By the inductive hypothesis, $T^{\prime}$ is a subgraph of $G$ with $\delta(G) = k+1$ (we know by the IH that $T^{\prime}$ is a subgraph of some graph with minimum degree $k$, so adding extra edges and necessary vertices to get minimum degree $k+1$ doesn't change this).
As $deg(w) \geq k+1$ and $T^{\prime}$ has $k-1$ vertices other than $v$, there exists a neighbor of $w$ not in $T^{\prime}$. We select such a vertex from $N(w)$ (the neighborhood of $w$) and add the edge to $T^{\prime}$ to give us a tree isomorphic to $T$ within $G$.