  We make progress on three long standing conjectures from the 1960s about path
and cycle decompositions of graphs. Gallai conjectured that any connected graph
on $n$ vertices can be decomposed into at most $\left\lceil
\frac{n}{2}\right\rceil$ paths, while a conjecture of Haj\'{o}s states that any
Eulerian graph on $n$ vertices can be decomposed into at most $\left\lfloor
\frac{n-1}{2}\right\rfloor$ cycles. The Erd\H{o}s-Gallai conjecture states that
any graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges.
  We show that if $G$ is a sufficiently large graph on $n$ vertices with linear
minimum degree, then the following hold.
  (i) $G$ can be decomposed into at most $\frac{n}{2}+o(n)$ paths.
  (ii) If $G$ is Eulerian, then it can be decomposed into at most
$\frac{n}{2}+o(n)$ cycles.
  (iii) $G$ can be decomposed into at most $\frac{3 n}{2}+o(n)$ cycles and
edges.
  If in addition $G$ satisfies a weak expansion property, we asymptotically
determine the required number of paths/cycles for each such $G$.
  (iv) $G$ can be decomposed into $\max
\left\{\frac{odd(G)}{2},\frac{\Delta(G)}{2}\right\}+o(n)$ paths, where $odd(G)$
is the number of odd-degree vertices of $G$.
  (v) If $G$ is Eulerian, then it can be decomposed into
$\frac{\Delta(G)}{2}+o(n)$ cycles.
  All bounds in (i)-(v) are asymptotically best possible.
