For every integer k≥ 1 and every varepsilon>0, there exists an integer r_0=r_0(k,varepsilon) such that every r-regular graph G on n vertices, with r≥ r_0, contains a k-regular subgraph H satisfying |V(H)|≥ (1-varepsilon)n.

Alon–Mubayi nearly spanning regular-subgraph conjecture

The Alon–Mubayi conjecture asks whether regular graphs always contain regular subgraphs that are nearly spanning. The Open Problem Garden recorded it as open in 2008, while a September 2026 preprint now claims a general resolution.

Known results

Petersen’s theorem gives spanning $2$ -regular subgraphs in every regular graph of even degree; iteration handles corresponding even-degree cases.
Alon, Friedland, and Kalai proved existence of regular subgraphs in sufficiently high-degree regular graphs, without a near-spanning bound.
Vizing’s theorem yields one special case via a largest color class in a $1$ -edge-coloring.
Alon proved another special case using the Minc conjecture, Bregman’s theorem, and the van der Waerden conjecture.

September 17, 2026 claimed resolution

Varun Sivashankar’s preprint Nearly Spanning Regular Subgraphs claims the conjecture for general $k$ and $r$ , improving the earlier parity-restricted cases and giving a best-possible bound in a notable special case. The claim is unverified because the preprint is unrefereed.

Current status (as of September 2026): The conjecture is claimed resolved for general $k$ and $r$ , but that resolution remains unverified.

Alon–Mubayi nearly spanning regular-subgraph conjecture

Primary source

Additional references

Progress summary

Solutions 0