Prove Matching of Size K

Question

The problem is as follows: Given a graph with n vertices, each having degree >= 2k, prove that a matching of size >= k exists. (n > 2k > 0)

My initial approach has been that if we can just find a path within the graph of length 2k, then simply alternating the edges in that path would result in a matching of size k. But now I'm not sure how to prove that such a path of length 2k exists.

Answer 1

Hint: Suppose $(v_1, \ldots, v_m)$ is a path. If $v_m$ has degree $\ge m$, there is some edge $(v_m, v_{m+1})$ so $(v_1, \ldots, v_{m+1})$ is a path.

Answer 2

Use induction. If you pick any edge $vw$, then deleting $v$ and $w$ from $G$ produces a graph with minimum degree $2k-2$.