Erdős problem 60 — wave 7c

Date: 2026-07-27 UTC

Claim labels

I use the requested labels throughout:

• (a) elementary-rigorous: proved here from definitions.
• (b) rigorous-modulo-named-theorem: relies on the cited theorem.
• (c) plausible/structural-unverified: explicitly not proved.
• (d) computational-only: exhaustive finite computation, with the software trust boundary stated.

Step 0: live-page check (performed before mathematics)

The Cloudflare-protected page was fetched through the Bright Data browser, not

through datacenter curl. I also fetched its “View the LaTeX source” page.

The following is the verbatim problem statement:

> Does every graph on \(n\) vertices with \(>\mathrm{ex}(n;C_4)\) edges contain

> \(\gg n^{1/2}\) many copies of \(C_4\)?

The page was OPEN, last edited 18 November 2025. Its verbatim mathematical

remarks were:

> Conjectured by Erdős and Simonovits, who could not even prove that at least

> \(2\) copies of \(C_4\) are guaranteed.

>

> The behaviour of \(\mathrm{ex}(n;C_4)\) is the subject of [765].

>

> He, Ma, and Yang [HeMaYa21] have proved this conjecture when

> \(n=q^2+q+1\) for some even integer \(q\).

The collision/stop markers were:

• 0 comments on this problem
• 0 claimed proofs for this problem
• Interested in collaborating None
• Currently working on this problem None
• likes: lof310, holyterror
• all “difficult / tractable / formalisable / working on formalising” markers:

None

Thus no stop condition applied. Source:

live problem and

live LaTeX source, both accessed

2026-07-27.

Outcome

(d) Define

The new finite result of this run is

The complete enumeration takes about 55 seconds on this VM and is reproduced

by erdos60_wave7c_verify.py.

(a) It is enough for the original asymptotic question to consider exactly

\(\operatorname{ex}(n,C_4)+1\) edges: from any graph with more edges, retain an

arbitrary spanning subgraph with exactly that many edges. Every \(C_4\) in the

subgraph remains a \(C_4\) in the original graph.

This finite result does not prove the uniform \(\Omega(\sqrt n)\) statement.

It extends the published exact table of Qiao--Zhan, whose theorem stops at

\(n=13\).

Literature audit

Original and cited sources

(b) The two Erdős references attached to the live page exist with the

following bibliographic records:

• P. Erdős, Some of my favourite unsolved problems, in *A Tribute to Paul

Erdős* (1990), 467--478,

DOI 10.1017/CBO9780511983917.039.

• P. Erdős, Some of my favorite solved and unsolved problems in graph theory,

Quaestiones Mathematicae 16 (1993), 333--350,

DOI 10.1080/16073606.1993.9631741.

The 1990 chapter itself was paywalled in this run, so I did not infer wording

from it. The current statement above comes from the live page. Qiao--Zhan's

primary paper reproduces Erdős's weaker question from pp. 472--473: whether

every graph with \(\operatorname{ex}(n,H)+1\) edges contains at least two

copies of \(H\).

(b) J. He, J. Ma and T. Yang, Some extremal results on 4-cycles,

J. Combin. Theory Ser. B 149 (2021), 92--108,

DOI 10.1016/j.jctb.2021.01.007,

was checked in the authors' full PDF. Its Theorem 1.3 says that for even

\(q\ge10^{12}\), every \((q^2+q+1)\)-vertex graph with

\(\frac12q(q+1)^2+1\) edges either has at least \(2q-3\) copies of \(C_4\), or

is an orthogonal polarity graph plus one edge, in which case it has

\(q-1,q\), or \(q+1\) copies. Combined with the exact extremal result, the

paper obtains

This is the precise infinite family behind the live-page summary.

(b) P. Qiao and X. Zhan, *On a problem of Erdős about graphs whose size is

the Turán number plus one*,

arXiv:2001.11723, published in

Bull. Aust. Math. Soc. 105 (2022), 177--187,

DOI 10.1017/S000497272100040X,

proves

It also records a one-\(C_4\) example at \(n=22\); thus even the weaker

“at least two” assertion has genuine finite exceptions.

(b) D. F. Daza, C. A. Trujillo and F. A. Benavides,

Sidon sets and \(C_4\)-saturated graphs,

arXiv:1810.05262, proves the desired

order of magnitude when one adds an edge to certain extremal Singer sum

graphs. This is construction-specific and is not a theorem about every

graph with \(\operatorname{ex}(n,C_4)+1\) edges.

(b) B. Ning and M. Zhai, *Counting substructures and eigenvalues II:

quadrilaterals, Electronic J. Combin.* 32(4) (2025), P4.1,

DOI 10.37236/12725, still calls the exact

\(\operatorname{ex}(n,C_4)+1\) assertion a longstanding conjecture and studies

a different spectral supersaturation problem.

(c) Exact-title, exact-formula, arXiv, journal, and forward-citation

searches found no later primary source claiming a uniform proof or

counterexample. A literature search cannot prove absence, so this is only an

honest search report. It agrees with the live page's OPEN status on

2026-07-27.

Extremal-number input

(b) The associated live problem 765 records the classical asymptotic

\(\operatorname{ex}(n,C_4)\sim\frac12n^{3/2}\), Füredi's exact polarity values,

and the stronger upper-bound history. It also records Ma--Yang's result that

for a positive-density set of \(n\),

for an absolute \(c>0\). The primary source is J. Ma and T. Yang,

Upper bounds on the extremal number of the 4-cycle,

Bull. London Math. Soc. 55 (2023), 1655--1667,

DOI 10.1112/blms.12810.

The Afzaly--McKay

extremal graph database

lists exact \(C_4\)-free extremal graphs through \(n=37\). I used it only as

an independent cross-check: the reported result below regenerates every graph

through \(n=18\) locally.

Elementary reductions

Counting cycles

For vertices \(u,v\), write \(c(u,v)=|N(u)\cap N(v)|\).

(a) Every \(C_4\) has exactly two pairs of opposite vertices, hence

The verifier checks every graph both with (1) and, independently, by examining

the three possible 4-cycles on every four-set.

For a \(C_4\)-free graph \(H\) and a nonedge \(xy\), let

(a) Adding \(xy\) creates exactly \(p_H(xy)\) copies of \(C_4\), all

containing \(xy\).

Exact-one lemma

(a) The following equivalence is the key to the finite lower bounds:

Proof. The reverse implication is immediate. Conversely, suppose \(G\) has

\(\operatorname{ex}(n,C_4)+1\) edges and one \(C_4\). Delete any edge \(xy\)

of that cycle. The resulting graph \(H\) has

\(\operatorname{ex}(n,C_4)\) edges and no \(C_4\), so it is extremal, and

adding \(xy\) creates exactly the deleted cycle. \(\square\)

Thus, enumerating only extremal \(C_4\)-free graphs suffices to rule out the

value 1. If some added nonedge creates exactly two cycles, it also gives the

matching upper bound \(h(n)\le2\).

Safe degree bounds for exhaustive generation

(a) Let \(H\) be \(C_4\)-free on \(n\) vertices, with \(m\) edges, and let

\(v\) have degree \(d\). Put \(A=N(v)\) and

\(B=V(H)\setminus(A\cup\{v\})\).

• \(H[A]\) has maximum degree at most 1, or two edges at a vertex of \(A\)

together with \(v\) make a \(C_4\). Thus \(e(A)\le\lfloor d/2\rfloor\).

• Every vertex of \(B\) has at most one neighbor in \(A\), or those two

neighbors together with \(v\) make a \(C_4\). Thus

\(e(A,B)\le|B|=n-1-d\).

• \(e(B)\le\operatorname{ex}(n-1-d,C_4)\).

Consequently

(a) Also, deleting a minimum-degree vertex gives

Equations (3)--(4) are why the exhaustive search is small. For example, an

extremal graph at each \(14\le n\le18\) has minimum degree at least 3; (3)

gives maximum degrees \(4,4,5,5,5\), respectively.

Exact computation

Completeness and trust boundary

(d) The verifier invokes nauty-geng 2.8.8 with -f, which generates one

representative of every unlabeled \(C_4\)-free graph satisfying the supplied

edge and degree bounds. It works inductively from \(n=4\):

1. earlier \(\operatorname{ex}(j,C_4)\) values used in (3)--(4) have already

been certified;

2. generation at the proposed extremal edge count finds at least one graph;

3. generation at one more edge finds none.

Edge deletion then rules out every still larger edge count. The computation

therefore rederives \(\operatorname{ex}(n,C_4)\), rather than trusting an OEIS

row or downloaded graph file. The irreducible trust boundary is the

correctness/completeness of nauty-geng and the local Python interpreter; this

is why the result is labeled (d), not (a).

The exact extremal census and saturation result is:

| \(n\) | \(\operatorname{ex}(n,C_4)\) | extremal isomorphism classes | histogram of \(p_H(xy)\) over all extremal \(H\), nonedges \(xy\) | minimum |

|---:|---:|---:|:---|---:|

| 14 | 27 | 1 | \(2:6,\ 3:37,\ 4:21\) | 2 |

| 15 | 30 | 2 | \(2:3,\ 3:108,\ 4:39\) | 2 |

| 16 | 33 | 2 | \(2:3,\ 3:84,\ 4:87\) | 2 |

| 17 | 36 | 1 | \(3:43,\ 4:51,\ 5:6\) | 3 |

| 18 | 39 | 1 | \(3:45,\ 4:51,\ 5:18\) | 3 |

(d) Every minimum is at least 2, so (2) proves \(h(n)\ge2\) throughout

\(14\le n\le18\).

Upper certificates

For \(n=14,15,16\), the following graph6 string encodes an extremal

\(C_4\)-free graph; adding the displayed edge produces exactly two \(C_4\)'s.

The standalone verifier contains a graph6 decoder written from the format

specification.

| \(n\) | extremal graph6 | add |

|---:|:---|:---|

| 14 | M?BDA_gFBHQKQoKc? | \((0,8)\) |

| 15 | N?BDA_gECUQaKWWcHc? | \((0,2)\) |

| 16 | `O?AAD?ocQDK_D_bIJAUC`` | \((0,10)\) |

(a) Here is a separate explicit 17-vertex witness, given by adjacency

lists (each edge appears twice in this presentation):

0: 6,9,15,16       1: 7,8,11,15       2: 3,7,10,13,14
3: 2,8,12,14       4: 5,9,11,12,13    5: 4,10,12,16
6: 0,11,14,16      7: 1,2,13,16       8: 1,3,12,15
9: 0,4,13,15      10: 2,5,14,15      11: 1,4,6,14
12: 3,4,5,8,16    13: 2,4,7,9        14: 2,3,6,10,11
15: 0,1,8,9,10    16: 0,5,6,7,12

It has 37 edges, and its only two \(C_4\)'s are

Its graph6 encoding is `P@?KB@Oa@GHOFGISEPe@oo_``.

(a) For \(n=18\), add vertex 17 adjacent to \(6,8,13\). In the

17-vertex graph,

Any new \(C_4\) through vertex 17 would give a common neighbor to two of

\(6,8,13\), so no new cycle appears. The new graph has \(37+3=40\)

edges, exactly \(\operatorname{ex}(18,C_4)+1\), and the same two cycles.

Combining these upper certificates with the exhaustive lower bound proves the

stated finite result (d).

As an additional cross-check, the same run obtains

The entries \(6\le n\le13\) agree with Qiao--Zhan.

Reproduction

Full standalone code:

runs/erdos60_wave7c_verify.py.

Run from the repository root:

python runs/erdos60_wave7c_verify.py

The completed run on this VM (Python 3.12.3, Debian nauty

2.8.8+ds-5) ended:

Compact upper certificates
  n=14: extremal graph6='M?BDA_gFBHQKQoKc?', add=(0, 8), cycles=2
  n=15: extremal graph6='N?BDA_gECUQaKWWcHc?', add=(0, 2), cycles=2
  n=16: extremal graph6='O?AAD?ocQDK_D_bIJA`UC', add=(0, 10), cycles=2
  n=17: explicit edges=37, cycles=2
  n=18: explicit edges=40, cycles=2

Exact table
  4:1 5:2 6:1 7:1 8:1 9:1 10:1 11:1 12:2 13:2 14:2 15:2 16:2 17:2 18:2
elapsed=55.124s
VERIFIED: h_C4(n,1)=2 for every 14<=n<=18

The verifier recomputes rather than loads certificates. It checks cycle

counts twice: explicitly over four-sets and through identity (1).

Clean reduction for the uniform problem

Let \(G\) have \(\operatorname{ex}(n,C_4)+1\) edges and \(T\) copies of

\(C_4\). Choose, among the spanning \(C_4\)-free subgraphs of \(G\), one

\(H\) with the maximum number of edges. Put

(a) Then

For every \(e\in R\), maximality of \(H\) means \(H+e\) contains a \(C_4\).

Since \(H\) is \(C_4\)-free, that cycle has its other three edges in \(H\).

Cycles obtained for different \(e\)'s are distinct. More precisely,

Thus any hypothetical counterexample with \(T=o(\sqrt n)\) contains a

\(C_4\)-free spanning graph only \(o(\sqrt n)\) edges below extremal.

The exact missing statement exposed by (5)--(6) is the following.

> Near-extremal multi-edge saturation lemma (not proved). There is an

> absolute \(c>0\) such that, for all sufficiently large \(n\), whenever

> \(1\le r

> \(|E(H)|=\operatorname{ex}(n,C_4)-r+1\), and \(H\) is a maximum

> \(C_4\)-free subgraph of \(H\cup R\) for a set \(R\) of \(r\) nonedges,

> then

> \[ > \sum_{e\in R}p_H(e)\ge c\sqrt n. > \]

(a) This lemma would settle problem 60: if \(r\ge c\sqrt n\), (6) is

already enough; otherwise the lemma and (6) are enough.

(c) He--Ma--Yang's polarity stability theorem is precisely the kind of

near-extremal structural input needed here, but it is presently available at

the decisive scale only for their special projective-plane orders. A

uniform version for arbitrary \(n\), together with a lower bound on the

selected saturation multiplicities \(p_H(e)\), is the unresolved bridge.

Why the standard global count stalls

Let

Since \(\binom{k}{2}\ge k-1\) for positive integers \(k\), (1) gives the

elementary bound

Convexity lower-bounds \(P_2(G)\) from the edge count.

(a) One extra edge changes the convex lower bound for \(P_2\) by only

\(\Theta(\sqrt n)\). To extract the target from (7), the pre-existing slack

below \(\binom n2\) must therefore also be \(O(\sqrt n)\), with a favorable

constant. Measured in edges, this demands \(O(1)\)-scale proximity to the

Reiman threshold \(\frac n4(1+\sqrt{4n-3})\), far more than a leading-term

asymptotic formula supplies.

(b) Ma--Yang's positive-density linear deficit from the Reiman-scale

benchmark changes the convex lower bound for \(P_2\) by order \(n^{3/2}\),

which overwhelms the order-\(\sqrt n\) gain from a single extra edge.

Consequently (7) can be vacuous at exactly

\(\operatorname{ex}(n,C_4)+1\) edges. Average supersaturation and average

nonedge saturation likewise do not control the particular low-saturation

edges selected in (6).

This is the precise wall: a proof needs local stability/saturation information

about all \(C_4\)-free graphs within \(O(\sqrt n)\) edges of the unknown

extremal configuration, not merely the asymptotic value of

\(\operatorname{ex}(n,C_4)\) or an average codegree inequality. Finite

enumeration cannot supply the required uniformity.

PARTIAL: Exhaustively verified the new exact cases \(h_{C_4}(n,1)=2\) for every \(14\le n\le18\), with explicit two-cycle witnesses and a 55-second standalone checker; the uniform \(\Omega(\sqrt n)\) problem remains open and reduces to the stated near-extremal multi-edge saturation lemma.