  We prove that for $k+1\geq 3$ and $c>(k+1)/2$ w.h.p. the random graph on $n$
vertices, $cn$ edges and minimum degree $k+1$ contains a (near) perfect
$k$-matching. As an immediate consequence we get that w.h.p. the $(k+1)$-core
of $G_{n,p}$, if non empty, spans a (near) spanning $k$-regular subgraph. This
improves upon a result of Chan and Molloy and completely resolves a conjecture
of Bollob\'as, Kim and Verstra\"{e}te. In addition, we show that w.h.p. such a
subgraph can be found in linear time. A substantial element of the proof is the
analysis of a randomized algorithm for finding $k$-matchings in random graphs
with minimum degree $k+1$.
