On vertex-disjoint paths in regular graphs (Q1753085)

Summary: 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.