Maximum edges in a girth-5 graph: is $\mathrm{ex}(n;\{C_3,C_4\})\sim(n/2)^{3/2}$? (Erdős #573)
Statement
For a graph $F$, let $\mathrm{ex}(n;F)$ denote the maximum number of edges in a graph on $n$ vertices that contains no copy of $F$ as a subgraph; for a family $\mathcal{F}$ of graphs, $\mathrm{ex}(n;\mathcal{F})$ forbids every member simultaneously. Write $C_3$ for the triangle and $C_4$ for the $4$-cycle, so that $\mathrm{ex}(n;\{C_3,C_4\})$ is the maximum number of edges in an $n$-vertex graph of girth at least $5$ (no cycle of length $3$ or $4$). Is it true that $$\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?$$ Equivalently, does $\mathrm{ex}(n;\{C_3,C_4\})/(n/2)^{3/2}\to 1$ as $n\to\infty$, where $(n/2)^{3/2}=2^{-3/2}n^{3/2}\approx 0.354\,n^{3/2}$?
Acceptance. FULLY RESOLVES: a complete proof that $\mathrm{ex}(n;\{C_3,C_4\})\sim(n/2)^{3/2}$ — i.e. a construction of $n$-vertex girth-5 graphs with $(1-o(1))(n/2)^{3/2}$ edges together with a matching upper bound, all steps given (machine-checkable in Lean/Coq preferred); OR a proof that the true asymptotic constant differs from $2^{-3/2}$. ADVANCES: improve the best rigorous leading constant on either side of $n^{3/2}$ relative to the bounds stated in the background (a construction beating the current best lower constant, or an upper bound below the trivial $\tfrac12$), with proof or a reproducible certificate; or extend the exact values of $\mathrm{ex}(n;\{C_3,C_4\})$ (OEIS A006856) to new $n$ via a verified search with an exhaustiveness certificate. Deliver the proof file, the explicit graph family with an edge-count and girth certificate, or the search code plus the verified extended table.
Background
Posed by Erdős [Er71, Er75] and Erdős–Simonovits [ErSi82], and reiterated by Erdős [Er93]. The motivation: Erdős–Simonovits proved $\mathrm{ex}(n;\{C_4,C_5\})=(n/2)^{3/2}+O(n)$, and Kővári–Sós–Turán [KST54] showed that the maximum number of edges in an $n$-vertex graph forbidding $C_4$ together with every odd cycle is also $\sim(n/2)^{3/2}$. This problem asks whether the same asymptotic constant survives when, among the odd cycles, only the triangle $C_3$ is forbidden. An elementary Moore-type bound already gives $\mathrm{ex}(n;\{C_3,C_4\})\le(n/2)\sqrt{n-1}\le(1+o(1))\tfrac12 n^{3/2}$ (a girth-5 graph of maximum degree $d$ needs $\ge d^2+1$ vertices), while incidence/polarity-type constructions supply girth-5 graphs with $\gg n^{3/2}$ edges; the conjecture pins the leading constant at $2^{-3/2}$, strictly below the trivial upper constant $\tfrac12$. The exact values of $\mathrm{ex}(n;\{C_3,C_4\})$ (maximum edges with girth $\ge 5$) are tabulated for small $n$ in OEIS A006856. Listed as open on erdosproblems.com/573 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number'); see also the general family case Erdős #574 (erdosproblems.com/574) and the pure $C_4$ problem Erdős #765 (erdosproblems.com/765). Attacker's tool: extend the exact sequence A006856 by exhaustive/ILP search and compare against $(n/2)^{3/2}$; build explicit dense girth-5 graphs (generalized-polygon incidence or polarity graphs) to raise the best lower constant; or a proof matching the Kővári–Sós–Turán asymptotic.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #573 (T. F. Bloom) | website |
| REF-02 | OEIS A006856 — maximal number of edges in an n-vertex graph of girth at least 5 (no C_3 or C_4) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.