Problem 113

If $G$ is bipartite then $\mathrm{ex}(n;G)\ll n^{3/2}$ if and only $G$ is $2$ -degenerate, that is, $G$ contains no induced subgraph with minimal degree at least 3.

Source: erdosproblems.com/113

Graph theory
Turán numbers

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN). The frontmatter standing is derived from the claim pages under claims/: Janzer's refereed disproof of the equivalence is accepted on its publication and the site's acceptance (claim page (Janzer, 2021)); OpenAI's refutation of the other direction of the equivalence, which also disproves the equivalence, is accepted on the site's acceptance of the same theorem for Problem 146 (claim page (OpenAI, 2026)); the label's Lean suffix is the site's formal status, reflecting the outside Lean formalization of Janzer's result that is linked on his claim page and that this corpus has not built.

Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter I, displays (1) and (2), the Erdős--Simonovits conjectures, pp. 333--334: "Simonovits and I conjectured [3] that if $G$ is a bipartite graph such that for every subgraph $G'\subseteq G$ the minimum degree of $G'$ is $\le2$ then (1) $T(n;G)<cn^{3/2}$ ; but if $G$ has a subgraph $G'$ every vertex of which has degree $\ge3$ then (2) $T(n;G)>n^{3/2+\epsilon}$ . (1) and (2) are both open and are probably very deep. I offer 500 dollars for a disproof of these conjectures"; the two conjectures together are the equivalence asked here. Library home: Erdős 1993.
ErSi84: Erdős, P. and Simonovits, M., Cube-supersaturated graphs and related problems. Progress in graph theory (Waterloo, Ont., 1982) (1984), 203-218.
Ja23b: Janzer, Oliver, Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3. Int. Math. Res. Not. IMRN (2023), 8478-8494.

Problem 113

Status

Proof claims

Discussion