  Magnant and Martin conjectured that the vertex set of any $d$-regular graph
$G$ on $n$ vertices can be partitioned into $n / (d+1)$ paths (there exists a
simple construction showing that this bound would be best possible). We prove
this conjecture when $d = \Omega(n)$, improving a result of Han, who showed
that in this range almost all vertices of $G$ can be covered by $n / (d+1) + 1$
vertex-disjoint paths. In fact, our proof gives a partition of $V(G)$ into
cycles. We also show that, if $d = \Omega(n)$ and $G$ is bipartite, then $V(G)$
can be partitioned into $n / (2d)$ paths (this bound in tight for bipartite
graphs).
