Erdős Problem #182
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A graph is \(k\) regular when every vertex in it has degree exactly \(k\). A graph contains a \(k\) regular subgraph if some nonempty subgraph, not necessarily induced or connected, is \(k\) regular.
Erdős and Sauer asked how many edges an \(n\) vertex graph may have while containing no \(k\) regular subgraph, for any fixed integer \(k\ge3\). In particular, is this extremal number at most \(n^{1+o(1)}\)? The question permits the \(k\) regular subgraph to use only a subset of the vertices and edges of the host graph.
A small example
A complete graph \(K_{k+1}\) is \(k\) regular. Thus any host graph containing \(K_{k+1}\) as a subgraph contains a \(k\) regular subgraph, but a general \(k\) regular graph need not be a clique. Checking for \(K_{k+1}\) alone would miss many witnesses.
A star \(K_{1,n-1}\) has many edges yet contains no 3-regular subgraph, since all edges are incident with its centre. It shows why merely exceeding a constant number of edges does not force a regular subgraph.
What is known
PROVED. Janzer and Sudakov, Resolution of the Erdős–Sauer problem on regular subgraphs (2023) showed that for each fixed \(k\ge3\) there is \(C(k)>0\) such that any \(n\) vertex graph with at least
edges contains a \(k\) regular subgraph. Consequently the extremal number for graphs avoiding \(k\) regular subgraphs is \(O_k(n\log\log n)\), which is indeed \(n^{1+o(1)}\).
Chakraborti, Janzer, Methuku and Montgomery (2024) improved the parameter dependence to \(C(k)\ll k^2\), sharp up to an absolute constant in the cited setting. A construction by Pyber, Rödl and Szemerédi explains why a logarithmic iterated factor cannot simply be removed across all cases by the existing argument.
A distinct Szemerédi question requires the resulting \(k\) regular subgraph to be connected. A disconnected union of two regular components answers the original question but not this stronger one. The maintained Erdős #182, updated March 2026, keeps this distinction explicit.
GCL's current state
Pinned and maintained status: PROVED. Original issue: #1451. The Janzer–Sudakov and 2024 strengthening are source-attributed; their entire proofs have not been independently reconstructed. Historic prize metadata is not an award determination.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor enumerates graphs on up to seven vertices, searches subgraphs for exactly \(k\) regular vertex-degree patterns with \(k=3\), and separately tests induced, not necessarily induced, and connected conventions. Acceptance: \(K_4\) is recognized as a 3-regular witness, a star has none, and no claim of a general \(n\log\log n\) theorem is inferred from finite enumeration.
Sources and claim boundaries
- Janzer–Sudakov, Forum of Mathematics, Pi 11 (2023), primary solution.
- Erdős #182, Chakraborti et al. [CJMM24b], Pyber–Rödl–Szemerédi [PRS95].
- Original GCL issue #1451.
No new regular-subgraph theorem, independent full proof certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1451 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.