Erdős Problem #146

Erdős Problem #146: the forest case and the four-cycle benchmark

Independent partial reconstruction, 23 September 2026.

1) Statement and known negative resolution

The proposed bound is $\operatorname{ex}(n,H)=O_H(n^{2-1/r})$ for every bipartite $r$-degenerate graph $H$. Here degeneracy means that every nonempty induced subgraph has a vertex of degree at most $r$. The current problem page records a connected, bipartite, 2-degenerate counterexample with extremal exponent strictly greater than $3/2$, attributed to an internal OpenAI model. This note does not reconstruct that counterexample. It proves the forest case and checks the sharp exponent for the particular graph $C_4$.

2) The complete $r=1$ argument

A graph is 1-degenerate precisely when it is a forest. A cycle supplies a subgraph of minimum degree two, so cannot occur in a 1-degenerate graph. Conversely, every nonempty forest has a vertex of degree at most one.

Let $H$ be a forest on $h\ge2$ vertices. Any graph of minimum degree at least $h-1$ contains a copy of $H$: embed each tree from a root, adding a vertex next to its already embedded parent. Before adding the last vertex, at most $h-2$ other used vertices can be neighbours of the parent, so an unused neighbour exists. At the start of a new component there is an unused vertex, since the host has at least $h$ vertices.

Consequently an $H$-free graph has, in every nonempty induced subgraph, a vertex of degree at most $h-2$. Delete vertices successively and count each edge when its first endpoint is deleted. This gives \[ \operatorname{ex}(n,H)\le(h-2)n, \] which is the required exponent one. The case of a one-vertex forbidden graph has no nonempty admissible host and is immaterial to the asymptotic assertion.

3) An exact counting bound for $C_4$

In a $C_4$-free graph, two distinct vertices have at most one common neighbour. If the degrees are $d_1,\ldots,d_n$ and the edge count is $e$, then \[ \sum_{i=1}^n\binom{d_i}{2}\le\binom n2. \] By Cauchy--Schwarz, $\sum d_i^2\ge4e^2/n$ and $\sum d_i=2e$. Hence \[ \frac{4e^2}{n}-2e\le n(n-1),\qquad e\le\frac n4\left(1+\sqrt{4n-3}\right)=O(n^{3/2}).\tag{1} \]

For a matching lower exponent, fix a prime $q$. Take one part to be the $q^2$ points $(x,y)\in\mathbb F_q^2$, the other the $q^2$ lines $y=ax+b$ with $(a,b)\in\mathbb F_q^2$, and join incident pairs. There are $2q^2$ vertices and $q^3$ edges. Two points with different first coordinates determine at most one such line, while two points with equal first coordinates lie on no common such line. Thus there is no four-cycle. Infinitely many primes give infinitely many orders at which the lower bound is a fixed positive multiple of $n^{3/2}$. Since $C_4$ is bipartite and 2-degenerate, the proposed exponent is attained for this particular forbidden graph.

4) Why this does not settle the general assertion

Degeneracy is not a bound on the maximum degree of either bipartition class. Even a tree formed from two adjacent degree-three vertices, each with two leaf neighbours, has a degree-three vertex in both classes. Thus a theorem assuming maximum degree at most $r$ on one side cannot be applied to every $r$-degenerate bipartite graph.

There is a separate logical distinction from Problem 147: a 3-regular graph with a small extremal number disproves a proposed minimum-degree lower bound, but is not 2-degenerate and does not disprove the present upper-bound assertion. Neither that example nor the special case $1$ supplies the required counterexample here.

ATTEMPT UNRESOLVED for reconstruction of the general disproof. The forest proof and the $C_4$ benchmark are complete, elementary, known arguments. No new result or independent formal verification is claimed.

5) Sources

https://www.erdosproblems.com/146, checked 23 September 2026, for the statement and current resolution. The proofs above use only greedy embedding, degree counting, and elementary arithmetic over a prime field; they do not rely on the cited counterexample.

The estimate credits the complete special cases and distinguishes the two degree conditions; the actual negative construction remains absent. It is subjective, not a correctness probability.

6) COMPLETION ESTIMATE

COMPLETION: 15%

Erdős Problem #146

1) ROUND-2 OBJECTIVE

Path A (positive theorem on a new solved subclass). Round-1 already handled the base case $r=1$ (forests). The best route in this continuation round is not to re-run dependent random choice from scratch, but to prove a new structural reduction showing that pendant trees can always be peeled off at a linear cost in the extremal number. This yields a broad new class of connected $bipartite$ graphs for which the conjectured exponent follows from a solved core, including all connected unicyclic bipartite graphs and, more generally, every connected graph whose $2$-core already lies in any solved family.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

1. If $H$ is a forest ($r=1$), then $\mathrm{ex}(n,H)=O_H(n)$.
2. The full conjecture is still open in general, and remains open even for $r=2$.
3. If $F$ is bipartite and one side of some bipartition has maximum degree at most $r$, then \[ \mathrm{ex}(n,F)=O_F(n^{2-1/r}). \]

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a simple but very effective tree-attachment reduction.

If a connected graph $H$ is obtained from a graph $F$ by attaching trees to vertices of $F$, then \[ \mathrm{ex}(n,H)\le \mathrm{ex}(n,F)+(|V(H)|-2)n. \] So any extremal upper bound for the core $F$ automatically propagates to the graph $H$ obtained by adding arbitrary pendant trees.

As a consequence, for connected graphs one may reduce Problem #146 to the case where the graph is equal to its own $2$-core (equivalently, has no leaves after iterative leaf stripping).

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap is that the first nontrivial case $r=2$ was still almost untouched except for special named families. The plan is:

1. Prove the tree-attachment reduction.
2. Apply it to the $2$-core of a connected graph.
3. Deduce new solved families immediately from existing core theorems.
4. In particular, settle every connected unicyclic bipartite graph (whose $2$-core is an even cycle).

5) WORK (ROUND-2)

Theorem 146.1 (tree-attachment reduction).

Let $F$ be a fixed graph, and let $H$ be a connected graph obtained from $F$ by attaching finitely many trees to vertices of $F$. Write $h:=|V(H)|$. Then for all $n$, \[ \mathrm{ex}(n,H)\le \mathrm{ex}(n,F)+(h-2)n. \]

Proof.

Let $G$ be an $n$-vertex graph with \[ e(G)>\mathrm{ex}(n,F)+(h-2)n. \] I claim that $G$ contains $H$.

Iteratively delete vertices of degree at most $h-2$ until no such vertex remains. Each deletion removes at most $h-2$ edges, so if all vertices were deleted then the total number of removed edges would be at most $(h-2)n$, contradicting \[ e(G)>\mathrm{ex}(n,F)+(h-2)n\ge (h-2)n. \] Hence a nonempty subgraph $G'\subseteq G$ survives with \[ \delta(G')\ge h-1. \] Moreover the total number of deleted edges is at most $(h-2)n$, so \[ e(G')> \mathrm{ex}(n,F). \] Since $|V(G')|\le n$ and $\mathrm{ex}(m,F)\le \mathrm{ex}(n,F)$ for $m\le n$, it follows that \[ e(G')>\mathrm{ex}(|V(G')|,F), \] so $G'$ contains a copy of $F$.

Fix such a copy of $F$ in $G'$. It remains to embed the trees attached to $F$. Root each attached tree at its attachment vertex in $F$, and order all vertices of $H\setminus V(F)$ so that each vertex appears after its parent.

Now embed the vertices of $H\setminus V(F)$ greedily in this order. Suppose at some stage we have already embedded $s<h$ vertices of $H$, and we want to embed a new vertex whose parent is already embedded at some vertex $u\in V(G')$. Since $\delta(G')\ge h-1$, vertex $u$ has at least $h-1$ neighbors in $G'$. At most $s-1\le h-2$ of these neighbors are already used (all embedded vertices other than $u$). Therefore $u$ has at least \[ (h-1)-(s-1)=h-s\ge 1 \] unused neighbors. Map the new vertex to one of them.

Proceeding inductively embeds all of $H$ into $G'$, hence into $G$. Therefore every $H$-free $n$-vertex graph has at most $\mathrm{ex}(n,F)+(h-2)n$ edges. $\square$

Corollary 146.2 ($2$-core reduction).

Let $H$ be a connected graph, and let $F$ be its $2$-core. Then \[ \mathrm{ex}(n,H)\le \mathrm{ex}(n,F)+(|V(H)|-2)n. \] In particular, if \[ \mathrm{ex}(n,F)=O(n^\gamma) \qquad\text{for some }\gamma\ge 1, \] then \[ \mathrm{ex}(n,H)=O(n^\gamma). \]

Proof.

A standard leaf-stripping decomposition of a connected graph says that $H$ is obtained from its $2$-core $F$ by attaching trees to vertices of $F$. Apply Theorem 146.1. $\square$

This is the main new structural advance: for connected graphs, all pendant trees are now completely eliminated from Problem #146.

Corollary 146.3 (new family from a solved core).

Let $H$ be a connected bipartite graph, and let $F$ be its $2$-core. If one side of some bipartition of $F$ has maximum degree at most $r$, then \[ \mathrm{ex}(n,H)=O_H(n^{2-1/r}). \]

Proof.

By the Alon--Krivelevich--Sudakov / Füredi theorem, \[ \mathrm{ex}(n,F)=O_F(n^{2-1/r}). \] Now apply Corollary 146.2. Since $2-1/r\ge 1$ for all $r\ge 1$, the extra linear term is negligible. $\square$

This strictly enlarges the standard "one side bounded-degree" class: attached trees may create arbitrarily large degrees away from the $2$-core, yet the optimal exponent still survives.

Corollary 146.4 (connected unicyclic bipartite graphs).

Let $H$ be a connected unicyclic bipartite graph, and let its unique cycle have length $2\ell$. Then \[ \mathrm{ex}(n,H)=O_H(n^{1+1/\ell}). \] In particular, \[ \mathrm{ex}(n,H)=O_H(n^{3/2}), \] which matches the Erdős--Simonovits conjectured exponent for $r=2$.

Proof.

The $2$-core of a connected unicyclic bipartite graph is exactly its unique even cycle $C_{2\ell}$. By Bondy--Simonovits, \[ \mathrm{ex}(n,C_{2\ell})=O_\ell(n^{1+1/\ell}). \] Now apply Corollary 146.2. Since $1+1/\ell\ge 1$, the extra linear term does not change the exponent. For $\ell\ge 2$ we have $1+1/\ell\le 3/2$, yielding the final bound. $\square$

So Round-2 settles an entire infinite family that was not treated in Round-1, and in fact gives the stronger exponent $1+1/\ell$ for each fixed cycle length $2\ell$.

Sharp obstruction isolated in this round.

If there exists any connected counterexample to Problem #146, then there also exists one whose $2$-core is a connected counterexample. Indeed, Corollary 146.2 shows that if the $2$-core $F$ of a connected graph $H$ satisfied the conjectured bound, then $H$ would satisfy it too.

Therefore the search for connected counterexamples may be reduced to graphs satisfying all of the following:

1. the graph is equal to its own $2$-core (equivalently, no leaf survives iterative stripping);
2. it is not covered by the one-side bounded-degree-on-the-core theorem;
3. it is not obtained from any currently solved core family merely by attaching trees.

Thus, for connected graphs, the genuinely open content lies entirely in core graphs of minimum degree at least $2$.

6) ADVERSARIAL VERIFICATION

1. Potential issue: counting removed edges in the pruning step. Each edge is removed exactly once, namely when its first endpoint is deleted. So the total number of removed edges is at most the sum of the deletion-time degrees, which is at most $(h-2)n$.
2. Potential issue: monotonicity of $\mathrm{ex}(n,F)$. If $m\le n$, every $m$-vertex $F$-free graph can be viewed as an $n$-vertex $F$-free graph by adding isolated vertices. Hence $\mathrm{ex}(m,F)\le \mathrm{ex}(n,F)$.
3. Potential issue: the greedy embedding might get stuck near the end. At the moment of embedding a new vertex, fewer than $h$ vertices are already used. Since the parent has at least $h-1$ neighbors and at most $h-2$ other used vertices exist, there is always an unused neighbor available.
4. Potential issue: disconnected graphs. The reduction theorem is stated only for connected graphs, and I have not silently extended it beyond that range. The unicyclic corollary is therefore completely safe, since unicyclic graphs are connected.
5. Potential issue: identifying the $2$-core of a unicyclic graph. For a connected unicyclic graph, iterative leaf stripping removes all trees attached to the unique cycle and leaves exactly that cycle. Since the graph is bipartite, the cycle length is even.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round-2 proves a new general reduction and a new infinite solved family:

1. If a connected graph $H$ is obtained from a graph $F$ by attaching trees, then \[ \mathrm{ex}(n,H)\le \mathrm{ex}(n,F)+(|V(H)|-2)n. \]
2. Therefore, for connected graphs, Problem #146 reduces to the case of graphs equal to their own $2$-core.
3. As a concrete consequence, every connected unicyclic bipartite graph $H$ with cycle length $2\ell$ satisfies \[ \mathrm{ex}(n,H)=O_H(n^{1+1/\ell})\le O_H(n^{3/2}). \]
4. More generally, any connected bipartite graph whose $2$-core lies in a presently solved class inherits the same conjectured exponent.

So the remaining open part of Problem #146 has now been narrowed to connected $r$-degenerate bipartite core graphs (minimum degree at least $2$) not accessible through solved core families.

8) COMPLETION ESTIMATE

COMPLETION: 74%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #146, erdosproblems.com/146, accessed 2026-03-07.
2. N. Alon, M. Krivelevich, and B. Sudakov, Turán numbers of bipartite graphs and related Ramsey-type questions, Combinatorics, Probability and Computing 12 $2003$, 477--494.
3. J. A. Bondy and M. Simonovits, Cycles of even length in graphs, Journal of Combinatorial Theory, Series B 16 $1974$, 97--105.

Erdős Problem #146 (Erdős--Simonovits conjecture for $r$-degenerate bipartite graphs)

1) FORMAL RESTATEMENT

For a fixed graph $H$, let $\mathrm{ex}(n,H)$ denote the Turán (extremal) number: the maximum number of edges in an $n$-vertex simple graph containing no copy of $H$ as a (not necessarily induced) subgraph.

A graph $H$ is $r$-degenerate if every (induced) subgraph of $H$ has a vertex of degree at most $r$; equivalently, there is an ordering of $V(H)$ in which each vertex has at most $r$ neighbors later in the order.

Conjecture (Erdős--Simonovits / Erdős). If $H$ is bipartite and $r$-degenerate, then \[ \mathrm{ex}(n,H)=O_H\left(n^{2-1/r}\right). \]

2) QUICK LITERATURE / CONTEXT CHECK

• A classic special case: if all degrees in one color class of $H$ are at most $r$, then $\mathrm{ex}(n,H)=O(n^{2-1/r})$ (Füredi; also Alon--Krivelevich--Sudakov $2003$ via dependent random choice).
• For general $r$-degenerate bipartite $H$, Alon--Krivelevich--Sudakov $2003$ proved a weaker universal bound $\mathrm{ex}(n,H)=O\left(n^{2-1/(4r)}\right)$.
• The conjectured exponent $2-1/r$ is known for large families of $r$-degenerate bipartite graphs, including all $r$-degenerate blow-ups of trees (Grzesik--Janzer--Nagy 2019/2022).
• For the $2$-degenerate grid graphs $F_t$ (the $t\times t$ planar grid), Bradač--Janzer--Sudakov--Tomon proved $\mathrm{ex}(n,F_t)=\Theta(n^{3/2})$, matching the conjectured exponent for $r=2$.

3) ATTACK PLAN

Proof track.

1. Settle the easiest case $r=1$ completely (forests), to validate the conjecture at the base level.
2. Recall the dependent random choice (DRC) template: show that if $G$ has many edges, then $G$ contains a bipartite pair $(U_1,U_2)$ where every $r$-tuple in $U_i$ has many common neighbors in $U_{3-i}$; then embed $H$ using a degeneracy ordering. This yields the known $2-1/(4r)$ exponent.
3. Identify what extra structure (supersaturation, random walks on auxiliary graphs, tensor power) is needed to upgrade the exponent from $2-1/(4r)$ to $2-1/r$.

Disproof track.

1. Search for candidate counterexamples among sparse bipartite graphs with bounded degeneracy but unusually large extremal exponent (e.g. graphs with "high complexity" in the sense used in the degenerate Turán literature).
2. Any disproof would require an explicit bipartite $r$-degenerate $H$ and a construction of $H$-free graphs with $\gg n^{2-1/r+\delta}$ edges.

4) WORK

Phase 1 sanity checks (tiny cases).

• $r=1$-degenerate graphs are forests. For a fixed tree $T$, it is classical and elementary that $\mathrm{ex}(n,T)=O(n)$.
• For $r=2$, the conjectured bound is $\mathrm{ex}(n,H)=O(n^{3/2})$ for every $2$-degenerate bipartite $H$. This is consistent with sharp results for $C_4$ and $K_{2,t}$, and with the proven case of grid graphs $F_t$.

A complete proof for $r=1$.

Beyond $r=1$.

For $r\ge 2$, the conjectured exponent $2-1/r$ is open in general. Known methods (e.g. dependent random choice) yield weaker exponents such as $2-1/(4r)$, and additional structure assumptions on $H$ (e.g. being a blow-up of a tree) allow proving the conjectured exponent.

5) VERIFICATION

• Theorem thm:146-r1 exactly matches the conjectured exponent for $r=1$.
• The degeneracy notion used (every induced subgraph has a vertex of degree $\le r$) is equivalent to the standard definition of degeneracy.
• No hidden assumptions: the proof uses only basic graph theory (minimum degree reduction and greedy tree embedding).

6) FINAL

UNRESOLVED. The full conjecture for all $r\ge 2$ remains open, but the base case $r=1$ is proved.

1. (i) Strongest fully proved partial result obtained:
   • Conjecture holds for $r=1$ (forests): $\mathrm{ex}(n,H)\le (|V(H)|-2)n$ (Theorem thm:146-r1).
   • (From the literature) general bound $\mathrm{ex}(n,H)=O(n^{2-1/(4r)})$ for $r$-degenerate bipartite $H$ (Alon--Krivelevich--Sudakov 2003), and sharp $\mathrm{ex}(n,H)=O(n^{2-1/r})$ for large families (e.g. $r$-degenerate blow-ups of trees).
2. (ii) Exact first gap: I do not have a proof (or counterexample) for the conjectured exponent $2-1/r$ for general bipartite $r$-degenerate graphs when $r\ge 2$.
3. (iii) Top 3 next moves:
   1. Strengthen DRC-type lemmas to produce larger structured bipartite subgraphs that support embedding of any $r$-degenerate $H$ with the optimal exponent.
   2. Develop supersaturation and counting of "degenerate" copies (as in the blow-up-of-trees results) for wider classes of $r$-degenerate graphs.
   3. Investigate potential counterexamples via constructions from algebraic graph theory / random algebraic methods, targeting $H$ with high "complexity" but still bounded degeneracy.
4. (iv) What a minimal counterexample would likely look like: a bipartite $r$-degenerate graph $H$ with bounded average degree but structured so that known embedding/counting arguments fail (e.g. forcing many "degenerate" partial embeddings), together with an explicit $H$-free construction achieving $\Omega(n^{2-1/r+\delta})$ edges.

7) COMPLETION ESTIMATE

9/10. The conjecture is central and has resisted existing general techniques; resolving it likely requires a new conceptual breakthrough or a definitive counterexample.