Logo
All Random Solved Random Open
SOLVED
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?
Asked by Erdős and Sauer. Resolved by Janzer and Sudakov [JaSu22], 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.

Additional thanks to: Antonio Girao