Problem Statement
Let $k\geq 3$. What is the maximum number of edges that a graph on $n$ vertices can contain if it does not have a $k$-regular subgraph? Is it $\ll n^{1+o(1)}$?
Categories:
Graph Theory
Progress
Asked by Erdős and Sauer. Resolved by Janzer and Sudakov [JaSu23], who proved that there exists some $C=C(k)>0$ such that any graph on $n$ vertices with at least $Cn\log\log n$ edges contains a $k$-regular subgraph.A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.
In [Er75] Erdős mentions a similar question of Szemerédi, in which the $k$-regular subgraph must be connected. Let $F(n,k)$ be the smallest number of edges on $n$ vertices which guarantee a connected $k$-regular subgraph. Erdős [Er75] proved $F(n,3) \ll n^{5/3}$.
Source: erdosproblems.com/182 | Last verified: January 14, 2026