HEXAGONbeta

Every C4C_4-free graph on 4949 vertices has a vertex of degree at most 66: an independent verification

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatoricscs.DM — Discrete Mathematics

Contributed by David Niedbala Giraudin

Version 2 / Nov 04, 2026 / CC BY 4.0

Abstract

ABSTRACT We give an independent proof that every graph on 4949 vertices containing no cycle of length four has a vertex of degree at most 66; equivalently, R(C4,K1,42)≤49R(C_4,K_{1,42})\le 49, hence R(C4,K1,42)=49R(C_4,K_{1,42})=49. In the notation of Erd\H{o}s, the least integer f(n)f(n) such that every graph on nn vertices with minimum degree at least f(n)f(n) contains a C4C_4 satisfies f(49)=7f(49)=7, while f(48)=f(50)=8f(48)=f(50)=8, so ff 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 kk, on C4C_4-free graphs with k2k^2 vertices and minimum degree at least kk, a symmetry reduction for k=7k=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)f(n+1)\ge f(n) for all sufficiently large nn (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.

Provenance statement

The research, the computations and the writing were carried out by the author with Claude (Anthropic). The hand proofs were checked by independent AI reviews; the computation was carried out by two separately written programs and checked by an independent log verifier and by DRAT proof certificates for a sample of refuted cases. No professional mathematician has reviewed the note yet.

Tools used

Anthropic
Claude Opus

References

  1. L. Boza, Exact values and bounds for Ramsey numbers of C4C_4 versus a star graph, arXiv:2409.12770v2 (2026).arXiv
  2. T. F. Bloom, Erdős Problems #85 and #552, https://www.erdosproblems.com .link
  3. P. Erdős, Some of my favorite solved and unsolved problems in graph theory, Quaestiones Math. 16 (1993), 333--350.
  4. A. J. Hoffman, R. R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960), 497--504.
  5. T. D. Parsons, Ramsey graphs and block designs I, Trans. Amer. Math. Soc. 209 (1975), 33--44.
  6. R. Walters, Claude Fable, GPT Sol, Astra, Claude Opus, A drop at forty-nine in Erdős Problem 85, Zenodo, doi:10.5281/zenodo.23325806 (12 October 2026), revised version 1.1, doi:10.5281/zenodo.23519149 (20 October 2026).DOI
  7. X. Zhang, Y. Chen, T. C. E. Cheng, Some values of Ramsey numbers for C4C_4 versus stars, Finite Fields Appl. 45 (2017), 73--85.
  8. S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin., Dynamic Survey DS1, revision 18 (2026).

Version history

  1. v1 · 8 pagesSubmitted by David Niedbala GiraudinInitial depositSupersededNov 04, 2026
  2. v2 · 8 pagesSubmitted by David Niedbala GiraudinSubmitted as a new versionCurrentNov 05, 2026