  In this paper we completely resolve the well-known problem of Erd\H{o}s and
Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph
can have without containing a $k$-regular subgraph, for some fixed integer
$k\geq 3$. We prove that any $n$-vertex graph with average degree at least
$C_k\log \log n$ contains a $k$-regular subgraph. This matches the lower bound
of Pyber, R\"odl and Szemer\'edi and substantially improves an old result of
Pyber, who showed that average degree at least $C_k\log n$ is enough.
  Our method can also be used to settle asymptotically a problem raised by
Erd\H{o}s and Simonovits in 1970 on almost regular subgraphs of sparse graphs
and to make progress on the well-known question of Thomassen from 1983 on
finding subgraphs with large girth and large average degree.
