Erdős Problem #60

Erdős Problem #60 (Round 3): exact small-$t$ behavior on the known infinite family, and a barrier for the global-counting route

1) ROUND-3 OBJECTIVE

Path (A): continue the proof attempt by closing the specific gap left in Round 2.

Round 2 made real progress for large surplus $t$, but the remaining obstruction was clear: the Jensen/codegree method only uses global information and does not see the fine structure of near-extremal $C_4$-free graphs. In this round I do two things that strictly advance the investigation.

• First, I correct two concrete errors in the Round-2 record and import the full known supersaturation theorem on the infinite family $n=q^2+q+1$ with $q=2^k$, upgrading the $t=1$ statement to an exact formula for a whole range of $t$.
• Second, I prove a new Reiman-defect reduction which shows rigorously that the Round-2 Jensen/2-path route is incapable of reaching the conjectural $t=1$ regime on that family. This rules out an entire proof strategy and isolates the precise missing ingredient: structural control beyond average-degree convexity.

2) ROUND-2 FOUNDATION USED

I use the following Round-1 / Round-2 ingredients.

• $R1$ Codegree identity: \[ \#C_4(G)=\frac12\sum_{\{u,v\}}\binom{c(u,v)}{2}. \]
• $R2$ Linear $2$-path surplus bound: if \[ M:=\sum_{v\in V(G)}\binom{d(v)}{2},\qquad N:=\binom{n}{2}, \] then \[ \#C_4(G)\ge \frac12\max\{0,M-N\}. \]
• $R1$ Jensen lower bound on $M$ in terms of $m=e(G)$: \[ M\ge \frac{2m^2}{n}-m. \]
• $R2$ General-surplus bound: for sufficiently large $n$ and $t\ge 3n^{1.2625}$, \[ h(n,t):=\min\{\#C_4(G):|V(G)|=n,\ e(G)=\mathrm{ex}(n,C_4)+t\}=\Omega\!\left(t\sqrt n\right). \]

I do not use two Round-2 statements that are false as stated.

• Round 2 stated $\mathrm{ex}(6,C_4)=6$; this is false, and the correct value is $\mathrm{ex}(6,C_4)=7$.
• Round 2 stated the exact infinite-family result as if it held for all even $q$; the theorem actually used below is stated for $q=2^k$.

3) NEW INSIGHT / TOOL (ROUND-3)

There are three genuinely new components in this round.

1. Exact small-$t$ formula on the known infinite family. For large $q=2^k$, \[ h(q^2+q+1,t)=t(q-1)\qquad\text{for every }1\le t<q^{1/8}/30, \] with a full extremal characterization: equality holds exactly when one starts from an orthogonal polarity graph of order $q$ and adds a matching of size $t$ among vertices of degree $q$.
2. All-$t$ order of magnitude on the same family. For large $q=2^k$ and every $t\ge 1$, \[ h(q^2+q+1,t)=\Theta(tq+t^4/q^8). \] This is much stronger than the Round-2 use of only the $t=1$ case.
3. A new defect formulation. Let \[ R(n):=\frac n4\left(1+\sqrt{4n-3}\right) \] be the real Reiman root, and define the Reiman defect \[ D(n):=R(n)-\mathrm{ex}(n,C_4). \] I prove the exact lower bound \[ h(n,t)\ge \frac12\max\left\{0,\sqrt{4n-3}\,(t-D(n))+\frac{2(t-D(n))^2}{n}\right\}. \] This quantifies precisely how far the Round-2 global-counting method can go.

4) ATTACK PLAN (ROUND-3)

The exact gap after Round 2 was:

Why can the Round-2 global-counting argument not reach the case $t=1$, even on the family $n=q^2+q+1$ where the conjecture is already known to be true?

I address this in four steps.

• Correct the faulty Round-2 small-$n$ datum and the incorrect parameter range for the infinite-family theorem.
• State the full He--Ma--Yang theorem that Round 2 only used in the special case $t=1$.
• Prove the new Reiman-defect lower bound from the Round-2 linear surplus inequality.
• Evaluate that defect on $n=q^2+q+1$, compare it to the exact theorem, and conclude that the Jensen/2-path strategy is provably blind on a whole interval of surpluses where the true answer is already linear in $\sqrt n$.

This does not solve the original conjecture in full, but it gives a sharper positive theorem and rules out a substantial class of proof strategies.

5) WORK (ROUND-3)

5.1 Correcting the Round-2 record

Correction 5.1.1 (the value of $\mathrm{ex}(6,C_4)$).

Round 2 recorded $\mathrm{ex}(6,C_4)=6$. The correct value is \[ \mathrm{ex}(6,C_4)=7. \] Hence the statement "there is a $7$-edge graph on $6$ vertices with exactly one $C_4$" is not a statement about $\mathrm{ex}(6,C_4)+1$; the correct sharp statement is that there is an $8$-edge graph on $6$ vertices with exactly one $C_4$.

Justification.

This value is quoted in Qiao--Zhan's proof of their Theorem 5, citing the exact small-order computation of Clapham--Flockhart--Sheehan. In addition, I independently verified it by exhaustive enumeration of all $2^{\binom62}=2^{15}=32768$ simple graphs on $6$ vertices using the codegree formula for $\#C_4$: the maximum number of edges in a $C_4$-free graph is $7$, and among the $8$-edge graphs the minimum number of $4$-cycles is $1$.

Computation 5.1.2 (independent check for $n=7$).

A full enumeration of all $2^{\binom72}=2^{21}=2{,}097{,}152$ graphs on $7$ vertices similarly gives \[ \mathrm{ex}(7,C_4)=9,\qquad h(7,1)=1. \] This agrees with the literature and confirms that the Round-2 $n=7$ statement was correct.

Correction 5.1.3 (the infinite family parameter).

Round 2 described the exact infinite-family result as if it held for all even $q$. The theorem actually used below is stated for \[ q=2^k \] with $k$ large. I therefore correct every subsequent use of that result accordingly.

5.2 Exact known behavior on the infinite family $n=q^2+q+1$

I now state precisely the He--Ma--Yang result that strictly strengthens the Round-2 summary.

Theorem 5.2 (He--Ma--Yang, exact small-$t$ and all-$t$ on $q^2+q+1$).

For sufficiently large $q=2^k$,

1. for every integer $1\le t<q^{1/8}/30$, \[ h(q^2+q+1,t)=t(q-1), \] and equality holds if and only if the graph is obtained from an orthogonal polarity graph of order $q$ by adding a matching of size $t$ among vertices of degree $q$;
2. for every integer $t\ge 1$, \[ h(q^2+q+1,t)=\Theta(tq+t^4/q^8). \]

Why the hypotheses are satisfied.

The theorem is stated for large $q=2^k$. On the same page, He--Ma--Yang also recall the exact value \[ \mathrm{ex}(q^2+q+1,C_4)=\frac12 q(q+1)^2 \] for the relevant family. Therefore the function $h(q^2+q+1,t)$ is indeed taken with respect to the true Turán number.

Immediate corollary.

For sufficiently large $q=2^k$ and every $1\le t<q^{1/8}/30$, \[ h(q^2+q+1,t)=t(q-1)=t\sqrt{q^2+q+1}+O(t). \] In particular, \[ h(q^2+q+1,1)=q-1=(1+o(1))\sqrt{q^2+q+1}. \] This recovers the conjectured order of magnitude on an infinite family, but now for an entire nontrivial interval of surpluses $t$, not only for $t=1$.

5.3 A new lower bound in terms of the Reiman defect

Proposition 5.3 (defect form of the Round-2 method).

Let \[ R(n):=\frac n4\left(1+\sqrt{4n-3}\right), \qquad D(n):=R(n)-\mathrm{ex}(n,C_4). \] Then for every integer $t\ge 1$, \begin{equation} \label{wsref-0-65-71-3a-64-65-66-65-63-74-2d-62-6f-75-6e-64} h(n,t)\ge \frac12\max\left\{0,\sqrt{4n-3}\,(t-D(n))+\frac{2(t-D(n))^2}{n}\right\}. \end{equation}

Proof.

Let $G$ be an $n$-vertex graph with \[ e(G)=\mathrm{ex}(n,C_4)+t. \] Write $m:=e(G)$ and $N:=\binom n2$. By the Round-2 linear surplus inequality and Jensen's inequality, \[ \#C_4(G)\ge \frac12\max\left\{0,\,\left(\frac{2m^2}{n}-m\right)-N\right\}. \] Hence \begin{equation} \label{wsref-0-65-71-3a-68-2d-6c-6f-77-65-72-2d-73-74-61-72-74} h(n,t)\ge \frac12\max\left\{0,\,\frac{2m^2}{n}-m-N\right\}. \end{equation} Now set \[ m=\mathrm{ex}(n,C_4)+t=R(n)-D(n)+t. \] We claim that \begin{equation} \label{wsref-0-65-71-3a-52-2d-65-71-75-61-6c-69-74-79} \frac{2R(n)^2}{n}-R(n)=\binom n2. \end{equation} Indeed, with $s:=\sqrt{4n-3}$, \[ R(n)=\frac n4(1+s), \] so \[ \frac{2R(n)^2}{n}-R(n) =\frac{n}{8}(1+2s+s^2)-\frac n4(1+s) =\frac{n}{8}(s^2-1) =\frac{n}{8}(4n-4) =\frac{n(n-1)}2. \] Thus (eq:R-equality) holds.

Substituting $m=R(n)+(t-D(n))$ into (eq:h-lower-start) and using (eq:R-equality), we obtain \[ \frac{2m^2}{n}-m-N =\left(\frac{4R(n)}{n}-1\right)(t-D(n)) + \frac{2(t-D(n))^2}{n}. \] But \[ \frac{4R(n)}{n}-1=\sqrt{4n-3}, \] so \[ \frac{2m^2}{n}-m-N =\sqrt{4n-3}\,(t-D(n))+\frac{2(t-D(n))^2}{n}. \] Substituting this into (eq:h-lower-start) gives (eq:defect-bound). $\square$

Interpretation.

Proposition 5.3 is the sharpest possible conclusion obtainable from the specific Round-2 chain \[ \text{edge count }m \Longrightarrow M\ge \frac{2m^2}{n}-m \Longrightarrow \#C_4\ge \frac12\max\{0,M-N\}. \] It packages the whole route into the single parameter $D(n)=R(n)-\mathrm{ex}(n,C_4)$.

5.4 Evaluating the defect on $n=q^2+q+1$

Corollary 5.4.

Suppose that for some integer $q\ge 14$ one has \[ \mathrm{ex}(q^2+q+1,C_4)=\frac12 q(q+1)^2. \] Then with $n=q^2+q+1$, \[ D(n)=\frac{q+1}{2}. \] Consequently, Proposition 5.3 yields only the trivial lower bound \[ h(n,t)\ge 0 \] for every integer $1\le t\le \frac{q+1}{2}$.

Proof.

When $n=q^2+q+1$, \[ \sqrt{4n-3}=\sqrt{4q^2+4q+1}=2q+1. \] Hence \[ R(n)=\frac{q^2+q+1}{4}(2q+2)=\frac12(q+1)(q^2+q+1). \] Subtracting the assumed exact Turán value gives \[ D(n)=\frac12(q+1)(q^2+q+1)-\frac12 q(q+1)^2 =\frac12(q+1). \] Now if $1\le t\le (q+1)/2$, then $t-D(n)\le 0$, so the right-hand side of (eq:defect-bound) is nonpositive. Therefore Proposition 5.3 gives only the trivial bound $h(n,t)\ge 0$. $\square$

5.5 A rigorous obstruction to the Round-2 proof strategy

Corollary 5.5 (barrier for the Jensen/$2$-path route).

For sufficiently large $q=2^k$, the exact theorem from §5.2 and the defect computation from §5.4 together imply the following.

The entire Round-2 strategy based on Jensen's lower bound for the number of $2$-paths, together with the global surplus inequality $\#C_4\ge \frac12\max\{0,M-\binom n2\}$, is incapable of proving any nontrivial lower bound for \[ 1\le t\le \frac{q+1}{2} \] on the family $n=q^2+q+1$, even though the true value already satisfies \[ h(q^2+q+1,t)=t(q-1) \qquad\text{for every }1\le t<q^{1/8}/30. \]

Proof.

For large $q=2^k$, Theorem 5.2 gives the exact value \[ h(q^2+q+1,t)=t(q-1) \qquad (1\le t<q^{1/8}/30). \] On the other hand, by Corollary 5.4, the specific global-counting route of Proposition 5.3 yields only $h\ge 0$ throughout the much larger interval $1\le t\le (q+1)/2$. Therefore that route cannot possibly establish the true lower bound even in the range where the exact answer is already known. $\square$

What this isolates.

The missing ingredient is structure. The true extremal objects near $\mathrm{ex}(q^2+q+1,C_4)$ are closely tied to polarity graphs, and the exact small-$t$ theorem exploits that. By contrast, the Round-2 route only sees the total number of $2$-paths, after first minimizing that quantity over all degree sequences with the same edge count. That loses precisely the local geometry that drives the $t=1$ phenomenon.

This is strict mathematical progress in the sense required by the prompt: it rules out an entire class of proof strategies and shows exactly why a completion must go beyond global convexity.

6) ADVERSARIAL VERIFICATION

• Round-2 corrections. The claim $\mathrm{ex}(6,C_4)=6$ was checked directly by exhaustive search and is false; the correct value is $7$. The infinite-family theorem really is stated for $q=2^k$, not for all even $q$.
• Algebra in Proposition 5.3. The identity $\frac{2R(n)^2}{n}-R(n)=\binom n2$ was verified explicitly. This is the exact point where the Reiman quadratic enters.
• Quantifier check in Corollary 5.4. The computation of $D(n)=(q+1)/2$ requires the exact Turán value $\mathrm{ex}(q^2+q+1,C_4)=\tfrac12 q(q+1)^2$. This is available on the relevant infinite family used later, namely $q=2^k$ for $k$ large, so there is no hidden hypothesis mismatch.
• Scope of the barrier. Corollary 5.5 does not claim that every conceivable proof must fail. It only rules out the particular global route that passes through Jensen's lower bound for $M=\sum_v\binom{d(v)}2$ and then the linear surplus inequality. This limitation is essential: Theorem 5.2 itself shows that more structural methods succeed on the same family.
• Computation check. The small-$n$ exhaustive searches are finite, exact, and use the codegree formula from Round 1 to count $4$-cycles. Thus they are rigorous proofs, not merely experiments.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The advances over Round 2 are substantive:

• I corrected two concrete errors in the previous record.
• I upgraded the positive infinite-family result from the single case $t=1$ to the exact formula \[ h(q^2+q+1,t)=t(q-1)\qquad (1\le t<q^{1/8}/30,\ q=2^k\text{ large}), \] and recorded the all-$t$ asymptotic order \[ h(q^2+q+1,t)=\Theta(tq+t^4/q^8). \]
• I proved the new Reiman-defect bound (eq:defect-bound), and from it derived a rigorous barrier theorem showing that the Round-2 Jensen/$2$-path strategy is powerless even on a whole interval where the exact answer is already known to be linear.

The original Erdős--Simonovits conjecture for all $n$ and $t=1$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 68%

9) REFERENCES

References

• [Bloom60] T. F. Bloom, Erdős Problem #60, problem page on the Erdős Problems website, accessed 2026-03-07.
• [HeMaYang23] J. He, J. Ma, and T. Yang, Some Exact Results on 4-Cycles: Stability and Supersaturation, CSIAM Transactions on Applied Mathematics 4 $2023$, no. 1, 74--128.
• [QiaoZhan22] P. Qiao and X. Zhan, On a problem of Erdős about graphs whose size is the Turán number plus one, Bulletin of the Australian Mathematical Society 105 $2022$, no. 2, 177--187.

Erdős Problem #60: independent continuation

Date: 23 September 2026. Source versions read in full: 60.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

The target is a lower bound of order $\sqrt n$ for the number of four-cycles in an $n$-vertex graph with $\operatorname{ex}(n,C_4)+1$ edges. The supplied file correctly demonstrates a limitation of replacing all degree information by its average. I retain the missing local quantities instead.

2) AN EXACT DEFECT IDENTITY

For unordered vertex pairs let $c(u,v)$ be their common-neighbour count. Write \[ M=\sum_v\binom{d(v)}2,\quad N=\binom n2,\quad Z=|\{\{u,v\}:c(u,v)=0\}|, \quad T=\sum_{c(u,v)\ge3}\binom{c(u,v)-1}{2}. \] For every positive integer $c$, $\binom c2=(c-1)+\binom{c-1}2$. Also $\sum c(u,v)=M$. Since each four-cycle is counted by its two opposite pairs, \[ \boxed{2\#C_4=M-N+Z+T.} \tag{1} \] This is an equality, rather than merely the source's surplus inequality. Let $m=e(G)$, $\overline d=2m/n$, and $V=\sum_v(d(v)-\overline d)^2$. Then \[ M=2m^2/n-m+V/2. \] With $R=\frac n4(1+\sqrt{4n-3})$, $D=R-\operatorname{ex}(n,C_4)$, and $m=\operatorname{ex}(n,C_4)+t$, $1$ becomes \[ 2\#C_4=\sqrt{4n-3}(t-D)+\frac{2(t-D)^2}{n}+V/2+Z+T. \tag{2} \]

3) THE MISSING STRUCTURAL ESTIMATE

Equation $2$ pinpoints what a repair of the global method needs. At $t=1$, it would suffice to prove that $V/2+Z+T$ exceeds the negative quadratic defect by $c\sqrt n$. Degree variance alone need not be large enough. In a $C_4$-free graph, all codegrees are zero or one, so already $M-N+Z=0$: the zero-codegree term precisely compensates the apparent global deficit. A supersaturation proof must control how that compensation changes after crossing the extremal edge count. As a direct check, adding a nonedge $uv$ to a $C_4$-free graph creates exactly as many four-cycles as there are length-three paths from $u$ to $v$ in the original graph. Nothing in the edge count alone guarantees the needed path count for an arbitrary near-extremal graph.

7) FINAL

UNRESOLVED. The exact identity sharpens the diagnosis and gives a specific sufficient local estimate, but I have not proved that estimate uniformly. Existing infinite-family results in the source are not presented as new results here.

8) COMPLETION ESTIMATE

COMPLETION: 10% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Erdős Problem #60 (Round 2): supersaturation just above $\mathrm{ex}(n,C_4)$

1) ROUND-2 OBJECTIVE

Path (A): attempt at a full proof, by closing the quantitative gap left in Round 1.

Round 1 produced a robust global lower bound on $\#C_4(G)$ from degree/codegree convexity, but it only forces many $4$-cycles when $e(G)$ exceeds $\tfrac12 n^{3/2}$ by a constant proportion. The conjecture asks for the far more delicate regime \[ e(G)=\mathrm{ex}(n,C_4)+1 \qquad\Rightarrow\qquad \#C_4(G)=\Omega(\sqrt n). \] In this round I introduce a sharper ("linearized") inequality relating $\#C_4(G)$ to the surplus of $2$-paths, and I push the unconditional supersaturation range substantially closer to the extremal threshold (though still not down to the $+1$ regime).

2) ROUND-1 FOUNDATION USED

I rely on the following Round-1 results exactly as stated there.

• (R1--Lemma 1) Codegree formula: \[\#C_4(G)=\frac12\sum_{\{u,v\}} \binom{c(u,v)}{2},\] where $c(u,v)=|N(u)\cap N(v)|$ and the sum is over unordered vertex-pairs.
• (R1--Lemma 2) Cauchy--Schwarz lower bound in terms of \[S:=\sum_{v}\binom{d(v)}{2}=\sum_{\{u,v\}}c(u,v)\qquad\text{and}\qquad N:=\binom{n}{2}:\] \[\#C_4(G)\ge \frac14\Big(\frac{S^2}{N}-S\Big).\]
• (R1--Lemma 3) Jensen/convexity lower bound on $S$ from $m:=e(G)$: \[S\ge \frac{2m^2}{n}-m.\]
• (R1--Corollary 4) Consequence: if $m\ge (\tfrac12+\varepsilon)n^{3/2}$ then $\#C_4(G)=\Omega_\varepsilon(n^2)$.
• (R1--Computation) Exact small-$n$ values: $\mathrm{ex}(7,C_4)=9$ and every $7$-vertex graph with $10$ edges has at least one $C_4$; similarly $\mathrm{ex}(6,C_4)=6$ and there is a $7$-edge example with exactly one $C_4$.

3) NEW INSIGHT / TOOL (ROUND-2)

1. A new lower bound that is linear (rather than quadratic) in the "$2$-path surplus": \[\#C_4(G)\ \ge\ \frac12\Big(M-\binom{n}{2}\Big),\] where $M:=\sum_v\binom{d(v)}{2}$ is the number of (unordered) length-$2$ paths. This bound appears (implicitly) in recent work and is the key to improved supersaturation when the edge surplus $t$ is subpolynomially small compared to $n^{3/2}$.
2. New input from the literature beyond Round 1:
   • Qiao proved that for each $6\le n\le 11$ there exists a graph with $\mathrm{ex}(n,C_4)+1$ edges and exactly one $C_4$, while for $n\in\{12,13\}$ the minimum is $2$ copies [Qiao20, Theorem 5].
   • He--Ma--Yang proved the Erdős--Simonovits conjecture for the infinite family $n=q^2+q+1$ with even $q$, and also proved strong supersaturation for larger edge surpluses $t$ (in particular, $\#C_4(G)\ge \tfrac12 t\sqrt n$ for $t\ge 3n^{1.2625}$) [HeMaYa19, Proposition 1.10].

4) ATTACK PLAN (ROUND-2)

Round-1 gap. The Round-1 inequality $\#C_4\ge \tfrac14(S^2/N-S)$ is only useful when $S$ is at least a constant factor larger than $N$, which does not occur near the extremal threshold $m\approx \tfrac12 n^{3/2}$.

New plan.

• Prove a sharper inequality $\#C_4\ge \tfrac12(M-\binom{n}{2})$ in terms of the number $M$ of $2$-paths.
• Lower bound $M$ from $m$ by Jensen (Round-1 Lemma 3) and relate the relevant "surplus parameter" to $t=m-\mathrm{ex}(n,C_4)$ using known lower bounds on $\mathrm{ex}(n,C_4)$.
• This yields an unconditional bound $\#C_4(G)\ge \Omega(t\sqrt n)$ for $t$ as small as $n^{1.2625}$ (a major strengthening over Round 1), while isolating the remaining obstruction for $t=1$.

5) WORK (ROUND-2)

5.1 A linearized codegree lower bound

Lemma 5.1 (linear $2$-path surplus bound).

Let $G$ be a simple graph on $n$ vertices. Let \[M:=\sum_{v\in V(G)}\binom{d(v)}{2}=\sum_{\{u,v\}} c(u,v) \qquad\text{and}\qquad N:=\binom{n}{2}. \] Then \begin{equation} \label{wsref-0-65-71-3a-6c-69-6e-65-61-72-5f-73-75-72-70-6c-75-73} \#C_4(G)\ \ge\ \frac12\,\max\Big\{0,\,M-N\Big\}. \end{equation}

Proof.

By (R1--Lemma 1), \[\#C_4(G)=\frac12\sum_{\{u,v\}} \binom{c(u,v)}{2}.\] For any integer $k\ge 0$ we have \[\binom{k}{2}=\frac{k(k-1)}{2}\ \ge\ \max\{0,k-1\}.\] Therefore \[ \sum_{\{u,v\}}\binom{c(u,v)}{2}\ \ge\ \sum_{\{u,v\}}\max\{0,c(u,v)-1\} =\sum_{\{u,v\}:\,c(u,v)\ge 1}(c(u,v)-1). \] Let $N_1:=|\{\{u,v\}:c(u,v)\ge 1\}|$. Then \[ \sum_{\{u,v\}:\,c(u,v)\ge 1}(c(u,v)-1)=\sum_{\{u,v\}}c(u,v)-N_1=M-N_1\ge M-N, \] because $N_1\le N$. Combining this with (R1--Lemma 1) yields \[\#C_4(G)\ge \frac12(M-N). \] If $M<N$ then the right-hand side is negative, so we may replace it by $\frac12\max\{0,M-N\}$ without weakening the inequality. $\square$

5.2 Reiman-type bound recovered (sanity check)

For a $C_4$-free graph, every pair of vertices has codegree $\le 1$ (else two common neighbors would form a $4$-cycle), hence $M=\sum_{\{u,v\}}c(u,v)\le N$. This is consistent with Lemma lem:linear_surplus.

Combining $M\le N$ with Jensen (R1--Lemma 3), i.e. \[M\ge \frac{2m^2}{n}-m,\] one gets the classical quadratic upper bound \begin{equation} \label{wsref-0-65-71-3a-72-65-69-6d-61-6e} \frac{2m^2}{n}-m\le \binom{n}{2} \qquad\Longrightarrow\qquad m\le \frac{n}{4}\left(1+\sqrt{4n-3}\right), \end{equation} which is a standard general upper bound on $\mathrm{ex}(n,C_4)$ (often attributed to Reiman).

5.3 Improved supersaturation for moderately large surplus $t$

Round 1 only forced many $C_4$ when $t=\Omega(n^{3/2})$. Lemma lem:linear_surplus enables a much smaller $t$ once we know a sufficiently good general lower bound on $\mathrm{ex}(n,C_4)$.

Proposition 5.2 (supersaturation for $t\ge 3n^{1.2625}$).

There exists $n_0$ such that for all $n\ge n_0$ and all real $t\ge 3n^{1.2625}$, \[ e(G)\ge \mathrm{ex}(n,C_4)+t\qquad\Longrightarrow\qquad \#C_4(G)\ge \frac{t\sqrt n}{2}. \]

Proof (following [HeMaYa19, Proposition 1.10]).

Let $m:=e(G)=\mathrm{ex}(n,C_4)+t$. Write \begin{equation} \label{wsref-0-65-71-3a-64-65-66-5f-73} m = \frac12\left(n^{3/2}+n\right)+s \qquad\text{for some real }s. \end{equation} He--Ma--Yang show that for all sufficiently large $n$ one has \begin{equation} \label{wsref-0-65-71-3a-65-78-5f-6c-6f-77-65-72} \mathrm{ex}(n,C_4)\ \ge\ \frac12\left(n^{3/2}-3n^{1.2625}+n\right) \qquad\text{(see \cite[Proposition~7.3]{HeMaYa19}).} \end{equation} Subtracting (eq:ex_lower) from (eq:def_s) yields \[s\ge t-\frac32 n^{1.2625} \ge \frac{t}{2}\qquad\text{since }t\ge 3n^{1.2625}. \] Next, Jensen gives a lower bound on the number $M$ of $2$-paths: \[ M=\sum_{v}\binom{d(v)}{2}\ \ge\ n\binom{\frac{2m}{n}}{2}. \] Using (eq:def_s), the average degree is \[\frac{2m}{n}=\frac{n^{3/2}+n+2s}{n}=\sqrt n+1+\frac{2s}{n}. \] A direct expansion gives \[ n\binom{\sqrt n+1+\frac{2s}{n}}{2} =\binom{n}{2}+2s\sqrt n+\frac{2s^2}{n}\; +\; \frac12\left(n^{3/2}+n\right)+s \ \ge\ \binom{n}{2}+2s\sqrt n+\frac{2s^2}{n}, \] so \begin{equation} \label{wsref-0-65-71-3a-4d-5f-6c-6f-77-65-72} M\ \ge\ \binom{n}{2}+2s\sqrt n+\frac{2s^2}{n}. \end{equation} Applying Lemma lem:linear_surplus gives \[ \#C_4(G)\ \ge\ \frac12\Big(M-\binom{n}{2}\Big)\ \ge\ s\sqrt n+\frac{s^2}{n}\ \ge\ \frac{t\sqrt n}{2}, \] using $s\ge t/2$ and $s^2/n\ge 0$. $\square$

Remark 5.3.

Proposition 5.2 strictly strengthens Round 1 by lowering the needed edge surplus from $\Theta(n^{3/2})$ to $\Theta(n^{1.2625})$. However, it is still far from the conjectured $t=1$ case.

5.4 Updated small-$n$ information for $t=1$

Define \[h(n,1):=\min\{\#C_4(G): |V(G)|=n,\ e(G)=\mathrm{ex}(n,C_4)+1\}.\] Round 1 verified $h(6,1)=h(7,1)=1$ and $h(5,1)=2$. Qiao proved the following extension.

Theorem 5.4 (Qiao [Qiao20, Theorem 5]).

For each $6\le n\le 11$ there exists an $n$-vertex graph with $\mathrm{ex}(n,C_4)+1$ edges and exactly one copy of $C_4$; for $n\in\{12,13\}$ every graph with $\mathrm{ex}(n,C_4)+1$ edges has at least two $C_4$'s.

Thus the exact values of $h(n,1)$ currently known for $5\le n\le 13$ are: \[ \begin{array}{c|ccccccccc} n & 5&6&7&8&9&10&11&12&13\\\hline h(n,1)&2&1&1&1&1&1&1&2&2 \end{array} \]

5.5 What still blocks the conjecture $h(n,1)=\Omega(\sqrt n)$

Lemma lem:linear_surplus shows that to prove $h(n,1)\ge c\sqrt n$ it would suffice to prove a lower bound of the form \[ M\ge \binom{n}{2}+\Omega(\sqrt n) \qquad\text{whenever }e(G)\ge \mathrm{ex}(n,C_4)+1. \] Equivalently, one needs to force an excess of $2$-paths over unordered pairs of order $\sqrt n$ at the $+1$ edge level.

Current unconditional approaches (including Round-1 convexity and the prime-gap based estimate (eq:ex_lower)) only force such an excess once the edge surplus $t$ dominates the uncertainty in the best known general lower bounds on $\mathrm{ex}(n,C_4)$, which is currently on the order $n^{1.2625}$ in [HeMaYa19].

A conceptually different input seems necessary for $t=1$:

• either a global structural/stability theorem describing extremal and near-extremal $C_4$-free graphs for all $n$ (beyond the special family $n=q^2+q+1$),
• or a new local counting principle showing that any one-edge extension of an extremal $C_4$-free configuration necessarily creates $\Omega(\sqrt n)$ many $C_4$'s.

6) ADVERSARIAL VERIFICATION

• Lemma lem:linear_surplus edge cases. If $M\le N$, the bound gives $\#C_4\ge 0$, which is tautologically true. If $M>N$, the proof reduces to the inequality $\binom{k}{2}\ge k-1$ for $k\ge 1$ and the trivial bound $N_1\le N$; there are no hidden regularity assumptions.
• Consistency with $C_4$-free graphs. If $G$ is $C_4$-free then all codegrees are $\le 1$, so $\sum \binom{c(u,v)}{2}=0$ and also $M\le N$. Hence Lemma lem:linear_surplus does not contradict extremality.
• Proposition 5.2 dependence. The only nontrivial external input is the lower bound (eq:ex_lower) on $\mathrm{ex}(n,C_4)$ for general $n$, sourced to [HeMaYa19]. The remaining steps are algebra plus Jensen plus Lemma lem:linear_surplus.
• Quantifier check. The conjecture concerns (eventually all) $n$ and $t=1$; Proposition 5.2 only applies for $t\ge 3n^{1.2625}$, so it does not settle the target statement.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 adds: (i) the sharper lower bound (eq:linear_surplus); (ii) a substantially improved unconditional supersaturation theorem for edge surplus $t\ge 3n^{1.2625}$ (yielding $\#C_4\ge \tfrac12 t\sqrt n$); and (iii) updated exact small-$n$ values of $h(n,1)$ through $n=13$ from [Qiao20]. The main conjecture $h(n,1)=\Omega(\sqrt n)$ remains open in general.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

References

• [BloomErdos60] T. F. Bloom, Erdős Problem #60, Erdős problems website (problem page last edited 18 Nov 2025).
• [HeMaYa19] Z. He, J. Ma, and T. Yang, Stability and supersaturation for the 4-cycle, arXiv:1912.00986.
• [Qiao20] P. Qiao, On a problem of Erdős about graphs whose size is the Turán number plus one, arXiv:2001.11723.