Tree with $k$ edges is a subgraph of any graph with all vertices of degree $\geq k$.

Question

Let $T$ be a tree with $k$ edges. Let $G$ be a graph where every vertex has a degree of at least $k$. Show that $T$ is a subgraph $G$.

I know this implies that in a graph where every vertex is at least $k$, you can find a copy of every tree with $k$ edges, but I'm stuck here.

Answer 1

Hint: Induction on $k$ (deleting a leaf to apply the induction hypothesis).

Answer 2

Here's a rough idea; I'll leave you to fill in the details.

We proceed algorithmically.

Pick a vertex $u$ in $T$ and map it to a vertex $\varphi(u)$ in $G$. Mark $u$ as "mapped" and $\varphi(u)$ as "used".

While there are unmapped vertices in $T$, pick a vertex $x$ in $T$ that is a neighbor of a mapped vertex $w$. Map it to a vertex $\varphi(x)$ in $G$ that is an unused neighbor of $\varphi(w)$. Mark $x$ as "mapped" and $\varphi(x)$ as "used".

What remains is to check (a) $\varphi(x)$ always exists, and (b) if $ab$ is an edge in $T$ then $\varphi(a)\varphi(b)$ is an edge in $G$.