Erdős problem 573 — wave 9r

Access date: 2026-07-28 UTC

Claim labels used throughout:

• (a) elementary-rigorous;
• (b) rigorous modulo the explicitly named theorem/source;
• (c) plausible or structural but unverified (including the non-exhaustiveness of a literature search);
• (d) computational-only.

0. Mandatory live-page gate

(d) I fetched both the rendered page and its LaTeX-source view through the Bright Data browser path, and cross-checked the rendered status panel in a full-page screenshot. The live page was erdosproblems.com/573, not the stale YAML.

(d) The page showed:

• status OPEN;
• last edit 18 January 2026;
• 0 comments and 0 claimed proofs;
• “Interested in collaborating: None”;
• “Currently working on this problem: None”;
• “This problem looks difficult: None”;
• “This problem looks tractable: None”;
• “The results on this problem could be formalisable: Dharun”;
• “I am working on formalising the results on this problem: None”.

Thus neither stop condition (claimed proof/solution/falsification or current worker) was present.

Verbatim live statement

(d) The following is copied verbatim from the page's LaTeX-source view:

Is it true that\[\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?\]

(b) The same live page lists the following known context: Erdős and Simonovits proved

and the bipartite \(C_4\)-free extremal number (equivalently, forbidding \(C_4\) and every odd cycle) is asymptotic to \((n/2)^{3/2}\). It points to problems 574 and 765 for the general case and for \(\operatorname{ex}(n;C_4)\), respectively.

1. Primary-source literature audit

Write

where \(z(n)\) is the maximum number of edges in an \(n\)-vertex bipartite \(C_4\)-free graph.

(b) The bibliographic identity of Kővári–Sós–Turán is verified at the publisher's record: T. Kővári, V. Sós, and P. Turán, “On a problem of K. Zarankiewicz,” Colloquium Mathematicum 3 (1954), 50–57.

(b) The original Erdős–Simonovits paper “Compactness results in extremal graph theory”, Combinatorica 2 (1982), 275–288, states its \(C_4,C_5\) result as Theorem 2. This checks the historical assertion on the live page against the primary paper rather than a secondary summary.

(b) Ma and Yang, “On extremal numbers of the triangle plus the four-cycle”, Forum of Mathematics, Sigma 13 (2025), e154 (also arXiv:2112.13689), explicitly say the leading-term conjecture is still widely open and that the best known upper bound remains

Their Theorem 1.3 proves, for an absolute \(c>0\) and every \(n\geq7\),

Thus the stronger formerly asked-for error \(f(n)=(n/2)^{3/2}+O(n)\) is false along suitable orders, but \(n^{5/4}=o(n^{3/2})\), so this does not decide the live leading-term question.

(b) Goedgebeur, Jooken, Joret, and Van den Eede, “Improved lower bounds on the maximum size of graphs with girth 5” (arXiv:2508.05562v1, 7 August 2025), state that the conjecture is still open, that the current asymptotic constants remain

and that exact values are known through \(n=53\). Their contribution is a heuristic lower-bound search for \(74\leq n\leq198\), not an exact method in that range.

(b) Garnick, Kwong, and Lazebnik, “Extremal graphs without three-cycles or four-cycles”, J. Graph Theory 17 (1993), 633–645, already determined the exact values through \(n=24\). The current Afzaly–McKay data page labels the values through \(n=53\) exact and labels \(n=54\) only \(f(54)\geq185\). Consequently, the exact \(n\leq15\) result below is an independent, reproducible derivation, not a claim of literature novelty.

(c) Searches through 2026-07-28 for the exact notation, “girth five,” and the triangle-plus-four-cycle title found no later primary source claiming an improved leading upper constant or a solution. This is an honest search result, not a proof that no unindexed paper exists.

2. Verified concrete result

Theorem

(a) For every \(1\leq n\leq15\),

The proof below is from scratch. It uses no catalogue or solver for the upper bounds. Explicit edge lists for every lower-bound witness are embedded in the companion verifier.

The local two-neighbourhood inequality

(a) Let \(G\) be an \(n\)-vertex graph containing neither \(C_3\) nor \(C_4\), and write \(d(v)\) for the degree of \(v\). For a fixed vertex \(v\), the sets

are pairwise disjoint:

• an intersection between \(N(v)\) and a second-neighbour set gives a

triangle;

• an intersection between the second-neighbour sets belonging to distinct

\(u,u'\in N(v)\), say at \(w\), gives the four-cycle \(v-u-w-u'-v\).

Therefore

or equivalently

(a) Summing (1) over \(v\) counts \(d(u)\) once for every neighbour of \(u\), and hence

Cauchy–Schwarz then gives the standard Moore-type bound

The cases \(1\leq n\leq10\)

(a) For each \(n\leq10\), the strict integer inequality

rules out the next edge by (2). Matching witnesses are: paths for \(n=2,3,4\), \(C_5\), \(C_6\), and, for \(n=7,8,9,10\), induced subgraphs of the Petersen graph with respectively \(8,10,12,15\) edges. The verifier constructs and checks each graph directly.

In every later case it suffices to rule out a graph with exactly the first forbidden number of edges: if a larger graph existed, deleting arbitrary edges would preserve \(\{C_3,C_4\}\)-freeness.

The case \(n=11\)

(a) Suppose \(e(G)=17\). Deleting a vertex and using \(f(10)=15\) gives

so \(\delta(G)\geq2\). Also \(\sum d(v)=34\), and the summed form of (1) gives \(\sum d(v)^2\leq110\).

Put \(x_v=d(v)-3\). Then

with every \(x_v\geq-1\). The only sorted integer degree multisets are

The standalone code independently enumerates all integer multisets and recovers exactly these four.

(a) Inequality (1) eliminates them:

• a degree-4 vertex in \((3^{10},4)\) sees degree sum at least \(12>10\);
• in \((2,3^8,4^2)\), its four cheapest possible neighbours have degree sum

\(2+3+3+3=11>10\);

• in \((2,3^9,5)\), the five cheapest have sum \(2+4\cdot3=14>10\);
• in \((2^2,3^6,4^3)\), every degree-4 vertex must use both degree-2

vertices and two degree-3 vertices to attain the only allowable sum \(2+2+3+3=10\). All three degree-4 vertices would then meet each degree-2 vertex, contradicting degree 2.

Thus \(f(11)\leq16\), and the embedded 16-edge witness gives equality.

The cases \(n=12\) and \(n=13\)

(a) If a 12-vertex graph had 19 edges, deleting any vertex and using \(f(11)=16\) would give \(\delta\geq3\). Since \(2e=38>36\), some vertex has degree at least 4. Its neighbours have degree sum at least \(4\cdot3=12>11\), contradicting (1). Hence \(f(12)=18\).

(a) If a 13-vertex graph had 22 edges, deleting any vertex and using \(f(12)=18\) would give \(\delta\geq4\). But then \(\sum d(v)\geq13\cdot4=52>44=2e\), a contradiction. Hence \(f(13)=21\).

The nontrivial finite case \(n=14\)

(a) Suppose \(e(G)=24\). Deletion and \(f(13)=21\) imply \(\delta(G)\geq3\). A vertex of degree at least 5 would have neighbour-degree sum at least \(5\cdot3=15>13\), violating (1). Thus every degree is 3 or 4. Since the degree sum is 48, there are six degree-4 vertices and eight degree-3 vertices.

Let \(H\) be the six degree-4 vertices and \(L\) the eight degree-3 vertices. For \(h\in H\), if \(r=d_H(h)\), then the degree sum of its neighbours is

Thus \(\Delta(G[H])\leq1\). Put

Degree sums on the two parts give

so \(a=c\), and \(0\leq a\leq3\).

(a) Count length-two paths through \(H\) with both endpoints in \(L\). There are \(2a\) vertices of \(H\) with three cross-neighbours and \(6-2a\) with four, so their number is

An adjacent pair in \(L\) has no common \(H\)-neighbour (triangle-free), and a nonadjacent pair has at most one (four-cycle-free). Hence

which forces \(a\geq2\). Only \(a=2,3\) remain.

(a) Now count length-two paths through \(L\) with endpoints in \(H\). For \(l\in L\), the cross-degree is \(3-d_L(l)\), so

• If \(a=c=2\), two disjoint edges in \(L\) minimize the left side, giving

\(4\binom22+4\binom32=16>13\). Adjacent edges give 17. So \(a\ne2\).

• If \(a=c=3\), (3) is at most 12. Three disjoint edges in \(L\) give

\(6\binom22+2\binom32=12\). Any nonmatching triangle-free three-edge graph uses at most five vertices and gives at least 13. Therefore \(G[L]\) is a matching of size 3 plus two isolated vertices.

Since \(a=3\) and \(\Delta(G[H])\leq1\), \(G[H]\) is also a perfect matching. Take an edge \(ll'\) of the matching in \(L\). Both \(l\) and \(l'\) have exactly two neighbours in \(H\). Their two \(H\)-neighbourhoods are disjoint, or there is a triangle through \(ll'\). Neither neighbourhood contains an edge of the \(H\)-matching, again by triangle-freeness. But four vertices chosen from three matched pairs necessarily contain both endpoints of some matched pair. Those two endpoints must be split between \(N_H(l)\) and \(N_H(l')\), yielding an alternating four-cycle

This final contradiction proves \(f(14)\leq23\); the explicit 23-edge witness proves equality.

The case \(n=15\)

(a) If \(e(G)=27\), deletion and \(f(14)=23\) give \(\delta(G)\geq4\). But \(2e=54<15\cdot4=60\), a contradiction. Thus the explicit 26-edge witness is optimal and \(f(15)=26\).

3. Standalone verification and independent audit

The self-contained verifier is runs/erdos573_wave9r_reverify.py. It uses only the Python standard library. Its substantive checks are:

1. validate all fifteen explicit edge lists and independently test every

triangle and every pair of common neighbours (the latter detects \(C_4\));

1. recompute all integer Moore inequalities for \(n\leq10\);
2. enumerate the four possible \(n=11\) degree multisets and reject each;
3. recompute the \(n=12,13,15\) deletion arithmetic;
4. enumerate all two- and three-edge graphs on the eight-vertex set \(L\)

used in the \(n=14\) proof, and exhaust the final two-subset matching obstruction.

Run:

python runs/erdos573_wave9r_reverify.py

(d) Fresh output:

VERIFIED exact ex(n,{C3,C4}) table through n=15
1:0 2:1 3:2 4:3 5:5 6:6 7:8 8:10 9:12 10:15 11:16 12:18 13:21 14:23 15:26
All witnesses, integer bounds, degree cases, and n=14 obstructions pass.

(d) Runtime was 0.12 wall seconds / 0.11 CPU seconds with peak RSS 11,868 KiB. SHA-256: 8b8291a7272d93c1743f78669d440872367053ee698278d19aad774fd73a7d5e.

(d) As a separate audit not used in the proof, nauty-geng -tf generated respectively

unlabelled extremal graphs for \(n=1,\ldots,15\), and zero graphs at the next edge count. These counts agree with the Afzaly–McKay catalogue wherever its displayed table applies.

4. Exact remaining wall

(a) Inequality (1), even after summation and optimal use of Cauchy–Schwarz, gives only

whereas the desired constant is \(1/(2\sqrt2)\). The standard two-neighbourhood argument therefore loses exactly a factor of \(\sqrt2\) in the leading constant. The small-\(n\) deletion arguments above exploit integrality and cannot supply a uniform asymptotic factor.

(c) A clean sufficient missing lemma would be the following sparse bipartisation statement:

Every \(n\)-vertex \(\{C_3,C_4\}\)-free graph has a cut containing all but \(o(n^{3/2})\) of its edges.

Indeed, the cut graph is bipartite and \(C_4\)-free, so it has at most \(z(n)=(n/2)^{3/2}+o(n^{3/2})\) edges; the lemma would immediately prove the live conjecture. No checked source proves this statement. Ma–Yang's \(\Omega(n^{5/4})\) non-bipartite gain shows that an \(O(n)\)-deletion version is false, while still being compatible with the displayed \(o(n^{3/2})\) scale. Allen–Keevash–Sudakov–Verstraëte's opposite conjecture \(\liminf f(n)/z(n)>1\) warns that even this sufficient lemma may be false.

(a) Finite exact computation, including the still-open \(n=54\) case, cannot by itself provide the uniform \(n\to\infty\) step. What remains is therefore not an omitted finite search but a genuinely global structural inequality (or an asymptotic counterconstruction with leading constant strictly above \(1/(2\sqrt2)\)).

PARTIAL: independently proved and reverified the exact table \(f(n)=0,1,2,3,5,6,8,10,12,15,16,18,21,23,26\) for \(1\leq n\leq15\); the asymptotic factor-\(\sqrt2\) upper-bound gap remains.