Skip to content

Erdős Problem #60

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, cycles.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Let \(\mathrm{ex}(n,C_4)\) denote the maximum number of edges in a simple \(n\)‑vertex \(C_4\)‑free graph. Erdős and Simonovits asked whether every graph with \(\mathrm{ex}(n,C_4)+1\) edges must contain \(\Omega(\sqrt n)\) copies of \(C_4\); their stronger formulation predicts \((1+o(1))\sqrt n\) copies.

The distinction between the two formulations matters. Erdős’ 1990 formulation uses an absolute constant \(c>0\), while the 1984 formulation asks for the asymptotic coefficient \(1\). The general problem remains open.

He, Ma, and Yang proved the conjectured scale for infinitely many orders. For \(q=2^k\), \(k\ge40\), they establish

\[ h(q^2+q+1)=q-1, \]

where \(h(n)\) is the minimum number of four-cycles in an \(n\)‑vertex graph with \(\mathrm{ex}(n,C_4)+1\) edges. Their proof uses stability of near-extremal \(C_4\)‑free graphs and orthogonal polarity graphs.

The remaining issue is uniformity over arbitrary \(n\). A natural reduction shows that any counterexample with \(o(\sqrt n)\) cycles would contain a \(C_4\)‑free graph only \(o(\sqrt n)\) edges below extremal, together with a small set of added edges whose individual saturation multiplicities sum to \(o(\sqrt n)\). Controlling those selected edges, rather than only average codegrees, is the principal unresolved step.

Six-section mathematical explanation

For a simple graph \(G\), define

\[ \mathrm{ex}(n,C_4) = \max\{|E(H)|: |V(H)|=n,\ C_4\nsubseteq H\}. \]

The threshold for forcing one \(C_4\) is \(\mathrm{ex}(n,C_4)+1\). Therefore the live-page condition

\[ |E(G)|>\mathrm{ex}(n,C_4) \]

is exactly the integer condition

\[ |E(G)|\ge\mathrm{ex}(n,C_4)+1. \]

The catalogue problem asks for constants \(c>0\) and \(n_0\) such that

\[ \forall n\ge n_0\ \forall G \left( |V(G)|=n,\ |E(G)|\ge\mathrm{ex}(n,C_4)+1 \Rightarrow \#C_4(G)\ge c\sqrt n \right). \]

The stronger historical form replaces \(c\sqrt n\) by \((1+o(1))\sqrt n\).

A small example

For vertices \(x,y\) let

\[ c_G(x,y):=|N_G(x)\cap N_G(y)|. \]

Then

\[ \#C_4(G) = \frac12 \sum_{\{x,y\}\subseteq V(G)} \binom{c_G(x,y)}2. \]

Proof: choose an unordered pair \(\{x,y\}\) of opposite vertices of a four-cycle. Two distinct common neighbors of \(x\) and \(y\) determine one four-cycle. Every four-cycle has exactly two opposite vertex-pairs, hence the factor \(1/2\).

This identity is also equivalent to

\[ 2\#C_4(G)=\sum_{\{x,y\}}\binom{c_G(x,y)}2. \]

Take \(G=K_{2,3}\). The unique unordered pair in the part of size \(2\) has codegree \(3\), contributing

\[ \binom32=3. \]

The three unordered pairs in the part of size \(3\) each have codegree \(2\), contributing

\[ 3\binom22=3. \]

Thus

\[ \#C_4(K_{2,3}) = \frac12(3+3)=3. \]

Directly, a four-cycle is obtained by choosing both vertices of the part of size \(2\) and any two of the three vertices in the other part:

\[ \binom22\binom32=3. \]

The two calculations agree.

What is known

For \(N=q^2+q+1\), orthogonal polarity graphs give \(C_4\)‑free graphs with

\[ \frac12q(q+1)^2 \]

edges when \(q\) is a suitable prime power. Füredi’s theorem gives equality for the relevant large even parameters. He–Ma–Yang prove that, for large even \(q\), every graph with one additional edge either has many four-cycles or is a polarity graph plus one edge.

For \(q=2^k\), \(k\ge40\), the exact minimum is

\[ h(N)=q-1. \]

Since

\[ \frac{q-1}{\sqrt{q^2+q+1}}\longrightarrow1, \]

the strongest asymptotic conjecture holds along this infinite sequence.

Suppose \(G\) has \(\mathrm{ex}(n,C_4)+1\) edges and only \(T\) four-cycles. Choose a maximum \(C_4\)‑free spanning subgraph \(H\subseteq G\), and write

\[ R=E(G)\setminus E(H),\qquad r=|R|. \]

Then

\[ |E(H)|=\mathrm{ex}(n,C_4)+1-r. \]

For every \(e\in R\), adding \(e\) to \(H\) creates at least one four-cycle. Let \(p_H(e)\) be the number created by \(e\). Distinct edges of \(R\) yield distinct cycles containing their respective added edge, so

\[ T\ge\sum_{e\in R}p_H(e)\ge r. \]

Thus \(r\ge c\sqrt n\) already proves the desired bound. A counterexample must therefore have \(r=o(\sqrt n)\) and hence an almost-extremal \(C_4\)‑free core \(H\).

The unresolved step is to show that such a core cannot have a selected set \(R\) of \(r\) nonedges with

\[ \sum_{e\in R}p_H(e)=o(\sqrt n). \]

Global codegree inequalities do not automatically control these particular selected nonedges.

GCL's current state

As of 2026-10-12, the maintained catalogue status is OPEN. GCL source assignment and evidence (source report pending posting). This is an editorial source audit, not GCL proof certification or mathematical acceptance.

The source lock should retain the pinned 1990 and 1993 Erdős references. The main mathematical blocker is the unproved uniform near-extremal multi-edge saturation lemma above. The full 1990 chapter was inaccessible in this run; its wording is therefore reported through the primary Qiao–Zhan quotation and the accessible 1984/1990 primary papers.

The original issue contains the authenticated RESULT/1 source report. This is source evidence, not independent mathematical certification or editorial admission.

What remains

For the fixed order \(n=7\) (only \(2^{21}\) labeled graphs):

  1. Determine \(\mathrm{ex}(7,C_4)\) by canonical generation of all \(C_4\)‑free graphs.
  2. Enumerate all non-isomorphic simple graphs with \(\mathrm{ex}(7,C_4)+1\) edges.
  3. Compute \(\#C_4(G)\) in two independent ways:
  4. direct enumeration of 4-vertex subsets;
  5. the codegree identity proved below.
  6. Output the exact value of \(h(7)\) and a graph6 witness attaining it.

Acceptance: every canonical graph is covered, both counting methods agree for every graph, and the reported minimum has a machine-checkable witness.

Falsification: a missed canonical graph, disagreement between the two counting methods, or a witness with a smaller verified cycle count.

Stopping rule: stop after the complete finite order‑\(7\) enumeration and independent certificate; do not infer the asymptotic conjecture from the finite result.

Sources and claim boundaries

Maintained problem #60; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.

The pinned catalogue metadata records the problem as open as of 2025-08-31. The live page was last edited 2025-11-18 and still labels the general problem open: Erdős Problem 60.

The cited 1990 source is Erdős, “Some of my favourite unsolved problems,” A Tribute to Paul Erdős, pp. 467–478, DOI 10.1017/CBO9780511983917.039. Its relevant weaker question is reproduced verbatim, with pp. 472–473 identified, by Qiao–Zhan: arXiv:2001.11723, lines 45–64. The full 1990 chapter was not accessible here, so that direct source remains PARTIAL.

The 1993 source is 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, cited by the live page at p. 335.

As of the latest dated status check located, 2026-08-01, the general \(\Omega(\sqrt n)\) assertion remains open; the unresolved remainder is uniformity over all sufficiently large \(n\): dated status record. No primary paper located through 2026-10-12 resolves the all‑\(n\) problem.

I reused the public live-page metadata, the public dated status audit, and the published He–Ma–Yang and Qiao–Zhan statements. I do not claim independent verification of their published proofs or of public finite-computation reports. The codegree identity and \(K_{2,3}\) calculation below are independently derived and checked.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1329 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction