HEXAGONbeta

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

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

Contributed by David Niedbala Giraudin ↗

Version 1 / Nov 04, 2026 / CC BY 4.0

Abstract

We prove 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, a value left open in the published tables. 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; the value f(48)=8f(48)=8 comes from an explicit 77-regular C4C_4-free Cayley graph on 4848 vertices, which is also an explicit lower-bound construction for the tabulated value R(C4,K1,41)=49R(C_4,K_{1,41})=49. Hence ff is not non-decreasing; to our knowledge no nn with f(n+1)<f(n)f(n+1)<f(n) was known before. 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. The 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.

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. 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.
  7. S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin., Dynamic Survey DS1, revision 18 (2026).

Version history

  1. v1Submitted by David Niedbala GiraudinInitial depositCurrentNov 04, 2026