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;

1. generation at the proposed extremal edge count finds at least one graph;
2. 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:

(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.

(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<c\sqrt n\), \(H\) is \(C_4\)-free with \(|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.