matching in k-regular graph

Question

I had been asked to prove that in k-regular graph exists a matching of size $n/4$ . I had read that answer Question about edge coloring and perfect matchings in regular graphs but I couldn't understand why if the graph is k+1 coloring it's implied that there is such matching.

Answer 1

Given a $k$-regular graph, we can construct a required matching $M$ consecutively picking to it a edge of the graph and removing from the graph the picked edge and all edges adjacent to it. Since each vertex of the graph has degree at most $k$, at each step we remove from the graph at most $2k-1$ edges. Since initially the graph has $nk/2$ edges, we can make at least $(nk/2)/(2k-1)>n/4$ steps.