Optimal path decompositions of sparse random graphs

Let odd(G) be the number of odd-degree vertices of a graph G. We prove that, if $p=o(1)$ and np/log n→∞, then with probability tending to one the random graph $G(n,p)$ has an edge decomposition into exactly odd(G)/2 paths. This confirms a conjecture of Glock, Kühn and Osthus from 2016. The proof combines a key lemma with cycle decompositions of random graphs.