math.CO — Combinatorics
Contributed by David Niedbala Giraudin
ABSTRACT
We give an independent proof that every graph on 49 vertices containing no cycle of length four has a vertex of degree at most 6; equivalently, R(C4,K1,42)≤49, hence R(C4,K1,42)=49. In the notation of Erd\H{o}s, the least integer f(n) such that every graph on n vertices with minimum degree at least f(n) contains a C4 satisfies f(49)=7, while f(48)=f(50)=8, so f is not non-decreasing. These values were first established by Walters, Claude Fable, GPT Sol, Astra and Claude Opus (12 October 2026), by a different case split whose computational part is checked by the formally verified checker cake_lpr and assembled in Lean; we were not aware of their work when this note was written. Our proof combines structural lemmas, valid for every odd k, on C4-free graphs with k2 vertices and minimum degree at least k, a symmetry reduction for k=7, and an exhaustive SAT search carried out by two separately written programs. Erd\H{o}s's question whether f(n+1)≥f(n) for all sufficiently large n (Problem 85 of erdosproblems.com) remains open.
COMMENTS
8 pages. Independent verification of f(49)=7 (Erdos Problem #85), first established by Walters, Claude Fable, GPT Sol, Astra and Claude Opus (Zenodo, doi:10.5281/zenodo.23325806, 12 October 2026). Ancillary folder anc/: pure-Python scripts, solver logs and SHA-256 hashes of all formulas. Technical assistance: Claude (Anthropic).
COMMENTAIRE DE VERSION (cas B seulement)
v2: credits the earlier proof of f(48)=8>f(49)=7 by R. Walters, Claude Fable, GPT Sol, Astra and Claude Opus (Zenodo, doi:10.5281/zenodo.23325806, 12 October 2026; v1.1 20 October 2026), of which the author was not aware when v1 was posted. Title, abstract, introduction (new paragraph "Related work") and Remark 3 updated; the 48-vertex graph is isomorphic to their witness. No mathematical change; ancillary files unchanged.
Primarily AI-generated textHuman understanding: no partsC4-free graphsErdos problemsRamsey numbersSAT solvingcomputer-assisted proofminimum degree