Claims

../

1985_12_01_pyber: Every n-vertex graph with at least a constant times k squared n log n edges contains a k-regular subgraph, so the maximum is n to the 1+o(1) and the yes-or-no part is answered yes; refereed in Combinatorica 5 (1985).

1995_01_01_pyber_rodl_szemeredi: A random bipartite construction with a constant times n log log n edges and no k-regular subgraph for any k at least 3, so the maximum is not linear in n; refereed in J. Combin. Theory Ser. B 63 (1995).

2022_04_26_janzer_sudakov: Theorem 1.2 gives, for every k, a constant C(k) such that average degree C(k) log log n forces a k-regular subgraph, so the maximum is at most a constant times n log log n and the answer is yes; Forum Math. Pi 11 (2023).

2024_11_18_chakraborti_janzer_methuku_montgomery: Average degree C r squared log log n forces an r-regular subgraph with one absolute constant C, and the r squared dependence is sharp, so the maximum is of order k squared n log log n for fixed k; Trans. Amer. Math. Soc. 2026.

2026_08_24_korsky: A proof claim posted on the site's proof-claim tab asserts that n to the 1+o(1) edges force an induced k-regular subgraph, hence a k-regular one, the problem's yes-or-no part; unreviewed, with the proof in an external file.

---