  Let $c\in (0, 1]$ be a real number and let $n$ be a sufficiently large
integer. We prove that every $n$-vertex $c n$-regular graph $G$ contains a
collection of $\lfloor 1/c \rfloor$ paths whose union covers all but at most
$o(n)$ vertices of $G$. The constant $\lfloor 1/c \rfloor$ is best possible
when $1/c\notin \mathbb{N}$ and off by $1$ otherwise. Moreover, if in addition
$G$ is bipartite, then the number of paths can be reduced to $\lfloor 1/(2c)
\rfloor$, which is best possible.
