If $G$ is a graph with $2k$ vertices, and every vertex of $G$ has degree at least $k$, how can I prove that $G$ has a perfect matching? (I used induction, and I am confused on Induction Conclusion: how can we use $2(k+1)$ vertices to deduce that $G$ is has a perfect matching? Do two new points mean there is a new edge that can be part of the perfect matching?)
I don't see how to get induction to work: when you match two vertices in a $2k+2$ graph where everything has degree at least $k+1$, what's left is a $2k$-vertex graph with every degree at least $k-1$, which is not good enough.
Hint: can you show that the graph is Hamiltonian? Why is this enough to ensure a perfect matching?