Problem 803

We call a graph $H$ $D$ -balanced (or $D$ -almost-regular) if the maximum degree of $H$ is at most $D$ times the minimum degree of $H$ .

Is it true that for every $m\geq 1$ , if $n$ is sufficiently large, any graph on $n$ vertices with $\geq n\log n$ edges contains a $O(1)$ -balanced subgraph with $m$ vertices and $\gg m\log m$ edges (where the implied constants are absolute)?

Source: erdosproblems.com/803

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site's label was DISPROVED on 2026-09-18; on 2026-10-07 the page printed no label to an anonymous reader, and the community database lists the problem as disproved (Lean), a status its file has carried since 26 September 2026. Alon's Proposition 2.1 ([Al08], Discrete Math. 308 (2008), no. 19, 4460--4472; refereed; author's preprint, p. 2): "For every $D>1$ and every $n>10^5$ , there is a graph $G$ with at most $2n$ vertices and at least $2n\log(2n)$ edges such that the following holds. For any $m$ and $d$ , if there is a subgraph $H$ of $G$ with $m$ vertices, average degree at least $d$ , and maximum degree at most $Dd$ , then $d<36(4\sqrt{\log m}+\log(64D)+18)$ ", introduced by "In this section we show that this is not true." A $D$ -balanced subgraph with $m$ vertices and average degree $d$ has maximum degree at most $Dd$ , so it has $e(H)=md/2<72m\sqrt{\log m}+18m\log(64D)+324m$ edges (a deduction made here), which is $o(m\log m)$ for fixed $D$ : no absolute $\epsilon$ works, whether $m$ is fixed and large or tends to infinity. The near-matching positive bound is Janzer and Sudakov's Theorem 6.3 (Forum Math. Pi 11 (2023), e19; refereed): given a positive integer $m_0$ , there are $n_0=n_0(m_0)$ and $\varepsilon=\varepsilon(m_0)>0$ for which each graph on $n\ge n_0$ vertices with $n\log n$ or more edges contains a $64$ -almost-regular subgraph whose vertex count $m$ is at least $m_0$ and whose edge count is at least $\varepsilon m\sqrt{\log m}/(\log\log m)^{3/2}$ , so Alon's bound is tight up to $\log\log$ factors. The frontmatter standing is derived from the accepted claim page Alon's disproof, whose acceptance evidence is the refereed journal, the refereed quotation by Janzer and Sudakov and the site's own commentary; Theorem 6.3 proves a weaker statement and settles nothing of the question, so it has no claim page.

Al08: Alon, Noga, Problems and results in extremal combinatorics---II. Discrete Math. 308 (2008), no. 19, 4460--4472, doi:10.1016/j.disc.2007.08.090 (Crossref record; the site's reference text gives "Discrete Math. (2008), 4460-4472"). Section 2, the printed problem and Proposition 2.1, p. 2 of the author's preprint (16 pp., pdfTeX of September 2007; the journal pagination is not in the preprint and the journal text is not held). Library home: Alon 2008; paged at Alon 2008, Proposition 2.1.
JaSu23: Janzer, Oliver and Sudakov, Benny, Resolution of the Erdős--Sauer problem on regular subgraphs. Forum Math. Pi 11 (2023), Paper No. e19, 13 pp.; doi:10.1017/fmp.2023.19 (received 2 November 2022, accepted 29 June 2023); arXiv:2204.12455 (v2, 15 August 2022). Section 6, Theorems 6.1--6.3, p. 11 of the journal version (the same page in arXiv v2). Library home: Janzer and Sudakov 2023; paged at Janzer and Sudakov 2023, Theorem 6.3 and, for the quotation of Alon, Janzer and Sudakov 2023, Theorem 6.2 (Alon, quoted).
ErSi70: Erdős, P. and Simonovits, M., Some extremal problems in graph theory. Combinatorial theory and its applications, I (Proc. Colloq., Balatonfüred, 1969), North-Holland (1970), 377--390; the open problem, p. 389; Definition 1 and Theorem 1, pp. 379--380. Library home: Erdős and Simonovits 1970; paged at Erdős and Simonovits 1970, Open problem (p. 389) and Erdős and Simonovits 1970, Theorem 1 (p. 380).
PRS95: Pyber, L., Rödl, V. and Szemerédi, E., Dense graphs without 3-regular subgraphs. J. Combin. Theory Ser. B 63 (1995), 41--54, doi:10.1006/jctb.1995.1004. Library home: Pyber and Szemerédi 1995. Alon's construction "is based on a modification of the technique of Pyber, Rödl and Szemerédi" ([Al08], p. 2): their random bipartite graph (printed pp. 42--43) joins each of the $n$ vertices of a class $B$ to exactly one random vertex in each of about $\tfrac12\log_{10}\log_{10}n$ classes $A_j$ of $n/2^{10^j}$ vertices, where Alon's uses classes $B_{i,j}$ of $n/2^i$ vertices; the paper's own almost-regular consequence (p. 42), graphs with $cn\log\log n$ edges and no subgraph with all degrees strictly between $D_x$ and $xD_x$ , is the $n\log\log n$ analogue of this question. The paper is context for the construction, not a result on the problem.

Problem 803

Status

Proof claims

Discussion