On vertex-disjoint paths in regular graphs

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