Erdős Problem #85
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory, ramsey theory.
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
A square in graph theory is a cycle of length four, not necessarily an induced square. Erdős #85 defines \(f(n)\) as the least integer such that every graph on \(n\) vertices whose minimum degree is at least \(f(n)\) contains a \(C_4\). Erdős asks whether \(f(n)\) is eventually nondecreasing:
for every sufficiently large \(n\). Knowing that \(f(n)\) is approximately \(\sqrt n\) does not settle this fine-scale monotonicity question; successive integer values can fluctuate.
A small example
On four vertices, minimum degree two forces a \(C_4\), while a triangle plus an isolated vertex is square-free. Thus \(f(4)=2\). On five vertices, the five-cycle has minimum degree two but no square. Consequently \(f(5)\ge3\). Since minimum degree three on five vertices forces a square, \(f(5)=3\).
The minimum-degree parameter cannot be replaced by average degree, and \(C_4\) need not be induced: any four distinct vertices joined in a four-cycle count, even when extra diagonals are present.
What is known
The conjectured eventual monotonicity is OPEN. The maintained problem page notes the relation with the asymmetric Ramsey number \(R(C_4,K_{1,t})\) and gives
The asymptotic follows from classical extremal estimates for four-cycle-free graphs and incidence-geometry constructions. These control the global scale but allow possible small downward fluctuations between adjacent integers.
The exact original statement also exists in the protected Formal Conjectures #85 file at revision 85f86371. It defines \(f(n)\) with an infimum over thresholds \(k\) and asserts eventual monotonicity. GCL directly read that source. Its admitted theorem contains a proof hole and is not a certified result.
GCL's current state
The original assignment is #1354. The pinned catalogue lists OPEN, and the maintained page (6 December 2025) agrees. The direct comparison shows the Lean target has the right overall quantifier order, but there has been no kernel replay, full semantic-equivalence audit or protected-statement admission. A GCL brute-force enumeration of all labelled graphs for \(n=4,5,6\) found respectively 54, 548 and 7984 graphs without a four-cycle, and verified \(f(4)=2\), \(f(5)=3\), \(f(6)=3\). The exhaustive fixture is saved in the CHAD QA staging area.
An authenticated RESULT/1 source report is posted on the original issue. It is unadjudicated source evidence, not independent proof certification or editorial admission.
What remains
A bounded independent-replay task is to enumerate all simple graphs on four, five and six vertices, reproducing the GCL fixture. For each, compute minimum degree and test whether any ordered four-tuple of distinct vertices forms a four-cycle. Let \(d_n\) be the greatest minimum degree among \(C_4\) free graphs; then \(f(n)=d_n+1\). Acceptance: a verified graph attaining \(d_n\) and a complete exhaustive upper-bound certificate, with independent \(f(4)=2\) and \(f(5)=3\) checks. Stop at \(n=6\) and make no inference about eventual monotonicity.
Sources and claim boundaries
- Erdős #85, original problem and extremal/related Ramsey bounds.
- Protected Formal Conjectures 85.lean, revision 85f86371, declaration inspected, proof absent.
- GCL original issue #1354.
No eventual-monotonicity proof, formal certification or editorial acceptance is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1354 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.