A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Question

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$.

Any solutions or hints are greatly appreciated. I'm so lost.

Answer 1

Here's a sketch of a proof. We proceed algorithmically: we begin with the empty subgraph $S$.

Initial step: Pick a vertex $v^{(T)}$ of the tree and match it up with any vertex $v^{(G)}$ in $G$. Mark $v^{(T)}$ as "used" and add $v^{(G)}$ to the subgraph $S$.

Recursive step: If there is any unused vertex $w^{(T)}$ in the tree which neighbors a used vertex $u^{(T)}$, we pair it up with a neighbor $w^{(G)}$ of $u^{(G)}$ in $G$ which is not already pair up. We add $w^{(G)}$ and the edge $w^{(G)}u^{(G)}$ to the subgraph. We mark $w^{(T)}$ as "used".

We complete the proof by arguing (a) that either $w^{(T)}$ and $u^{(T)}$ exist, or we are "done" (since trees are connected), (b) that $w^{(G)}$ always exists (due to the degree constraint), and (c) the subgraph $S$ is isomorphic to $T$ via the isomorphism $x^{(T)} \mapsto x^{(G)}$.