2
$\begingroup$

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?)

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.