  We prove that for every $\varepsilon > 0$ there is $c_0$ such that if $G\sim
G(n,c/n)$, $c\ge c_0$, then with high probability $G$ can be covered by at most
$(1+\varepsilon)\cdot \frac{1}{2}ce^{-c} \cdot n$ vertex disjoint paths, which
is essentially tight. This is equivalent to showing that, with high
probability, at most $(1+\varepsilon)\cdot \frac{1}{2}ce^{-c} \cdot n$ edges
can be added to $G$ to create a Hamiltonian graph.
