$k$ regular graph with $(k+1)^2 -1$ vertices and matching saturates $n-k$ vertices

Question

We have a $k$ regular graph $G$ with $n=(k+1)^2-1$ vertices and $k \geq 1$ is even. Prove that the graph has a matching saturates at least $n-k$ vertices.

My first intuition is to use the defect version of Tutte's Theorem. However, I am stuck on where to start. Can anyone help me with that?

Answer 1

Suppose $G$ has $m$ components. Then each component has at least $k+1$ vertices (since $G$ is $k$ regular) and thus we have $$m(k+1)\leq (k+1)^2-1\implies m\leq k$$

Since each component has Euler circle (each vertex has even degree) we see that at most one vertex (in particular component if it has odd number of vertices) does not have a matching pair.

So we have in total at most $m$ vertices without a matching pair so at least $n-m \geq n-k$ vertices are saturated.