Resolution of the Erdős–Sauer problem on regular subgraphs

Abstract

In this paper, we completely resolve the well-known problem of ErdÅ 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. We prove that any n-vertex graph with average degree at least contains a k-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least is enough. Our method can also be used to settle asymptotically a problem raised by ErdÅ 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.