Problem 551

Prove that

R(C_k,K_n)=(k-1)(n-1)+1

for $k\geq n\geq 3$ (except when $n=k=3$ ).

Source: erdosproblems.com/551

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem DECIDABLE, which the site defines as resolved up to a finite check. The label is a statement about the shape of what remains, not a theorem; it is recorded as the accepted partial claim page Keevash, Long and Skokan 2021, whose Covers. states the finite check, and the page records what is proved and what remains. A full proof of the identity, closing that check, is given by the OpenAI release's preprint of 25 September 2026 and accepted on the claim page OpenAI 2026 on its Lean proof, which this corpus built, checked for axioms and found identical to the release's comparator challenge; the preprint itself is unrefereed and unreviewed. The derived standing, solved, proved, departs from the site's DECIDABLE by counting that accepted full claim; the refereed partial claims alone leave the finite check open, which is what the label records. Proved, in refereed sources, each an accepted partial claim on its refereed publication alone: the identity for $k\ge n^2-2$ ([BoEr73] Theorem 4, Bondy and Erdős 1973), for $k\ge4n+2$ when $n\ge4$ ([Ni05], preprint Theorem 1, Nikiforov 2005) and for $k\ge C\log n/\log\log n$ with an absolute constant $C$ that is not computed ([KLS21] Theorem 1.1), which covers every $k\ge n$ once $n$ exceeds a threshold $n_0(C)$ that the paper does not name; the case $n=3$ is the classical $R(C_k,K_3)=2k-1$ for $k>3$ (quoted from Chartrand and Schuster on p. 47 of [BoEr73]), the cases $n=4$ , $5$ , $6$ are reported settled for all $k\ge n$ by the introductions of [Ni05] and [KLS21] (sources not held), and the literature list of [OAI26] (Section 1.1) reports $n=7$ settled for all $k\ge7$ by Chen, Cheng and Zhang (2008) and, for $n=8$ , the lengths $k=8$ , $9$ and $10\le k\le15$ settled by papers of 2007--2023 (sources not held). Left by the refereed results: for each of the finitely many $n$ with $8\le n<n_0(C)$ , the cycle lengths $k$ with $n\le k\le\min\{4n+1,\lceil C\log n/\log\log n\rceil-1\}$ , less the settled $n=8$ cases, so that for $n=8$ the lengths $16\le k\le33$ below the threshold of [KLS21] remain: a finite set of pairs whose extent is unknown because $C$ is not explicit. No refereed source closes it; the accepted 2026 result closes all of it. The one site comment (1 September 2025) describes the state before the release: reduced to a finitary problem, still open.

EFRS78: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., On cycle-complete graph Ramsey numbers. J. Graph Theory 2 (1978), no. 1, 53--64, doi:10.1002/jgt.3190020107; Section 7, printed p. 64. Library home: Erdős 1978.
BoEr73: Bondy, J. A. and Erdős, P., Ramsey numbers for cycles in graphs. J. Combinatorial Theory Ser. B 14 (1973), no. 1, 46--54, doi:10.1016/S0095-8956(73)80005-X; Theorem 4, p. 52; Theorem 5, p. 53. Library home: Bondy and Erdős 1973; result page Theorem 4.
Ni05: Nikiforov, V., The cycle-complete graph Ramsey numbers. Combin. Probab. Comput. 14 (2005), no. 3, 349--370, doi:10.1017/S096354830400642X (published 11 April 2005); arXiv:math/0404501v1 (27 April 2004, 23 pages, "accepted in Comb. Prob. and Comp"). The journal article is paywalled; the preprint's Theorem 1 (p. 2) is the statement cited here, and the journal version numbers its statements differently. Library home: Nikiforov 2005; result page Theorem 1.
KLS21: Keevash, P., Long, E. and Skokan, J., Cycle-complete Ramsey numbers. Int. Math. Res. Not. IMRN 2021, no. 1, 275--300, doi:10.1093/imrn/rnz119 (online 10 July 2019; the site's reference gives the pages as 277--302); arXiv:1807.06376v1 (17 July 2018, the only arXiv version); Theorem 1.1, p. 2 of the preprint. Library home: Keevash and Skokan 2021.
ChHa72: Chvátal, V. and Harary, F., Generalized Ramsey theory for graphs, III. Small off-diagonal numbers. Pacific J. Math. 41 (1972), 335--345. The lower bound; not held; quoted here from [KLS21], p. 2.
Sch03: Schiermeyer, I., All cycle-complete graph Ramsey numbers $r(C_m,K_6)$ . J. Graph Theory 44 (2003), 251--260. The range $k\ge n^2-2n$ and the case $n=6$ ; not held; second-hand through [KLS21] (p. 2) and [Ni05] (p. 1). - Small orders, second-hand through [KLS21] (p. 2, references [24, 43, 52, 8, 44]) and [Ni05] (p. 1), none held: Faudree, R. J. and Schelp, R. H., All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313--329, and Rosta, V., On a Ramsey type problem of J. A. Bondy and P. Erdős, I and II, J. Combin. Theory Ser. B 15 (1973), 94--120 ( $n=3$ ); Yang, J. S., Huang, Y. R. and Zhang, K. M., The value of the Ramsey number $R(C_n,K_4)$ is $3(n-1)+1$ ( $n\ge4$ ), Australas. J. Combin. 20 (1999), 205--206 ( $n=4$ ); Bollobás, B., Jayawardene, C. J., Yang, J. S., Huang, Y. R., Rousseau, C. C. and Zhang, K. M., On a conjecture involving cycle-complete graph Ramsey numbers, Australas. J. Combin. 22 (2000), 63--71 ( $n=5$ ); Schiermeyer, I., The cycle-complete graph Ramsey number $r(C_5,K_7)$ , Discuss. Math. Graph Theory 25 (2005), 129--139. - Exact values for $n=7$ and $n=8$ , second-hand through the literature list of [OAI26] (Section 1.1 and its bibliography), none held: Chen, Y., Cheng, T. C. E. and Zhang, Y., The Ramsey numbers $R(C_m,K_7)$ and $R(C_7,K_8)$ , European J. Combin. 29 (2008), no. 5, 1337--1352, doi:10.1016/j.ejc.2007.05.007 ( $n=7$ , all $k\ge7$ ); Jaradat, M. M. M. and Alzaleq, B. M. N., The cycle-complete graph Ramsey number $r(C_8,K_8)$ , SUT J. Math. 43 (2007), 85--98, and Zhang, Y. and Zhang, K. M., The Ramsey number $R(C_8,K_8)$ , Discrete Math. 309 (2009), 1084--1090 ( $k=8$ ); Bataineh, M. S. A., Jaradat, M. M. M. and Al-Zaleq, L. M. N., The cycle-complete graph Ramsey number $r(C_9,K_8)$ , ISRN Algebra 2011, Art. ID 926191 ( $k=9$ ); Baniabedalruhman, A., The cycle-complete graph Ramsey numbers $R(C_n,K_8)$ , for $10\le n\le15$ , Jordan J. Math. Stat. 16 (2023), no. 4, 703--718 ( $10\le k\le15$ ).
OAI26: OpenAI, Cycle--clique Ramsey numbers. OpenAI Math Release preprint, 25 September 2026, 41 pages, in the release's folder preprints/Cycle-clique-Ramsey-numbers-September-25-2026 (PDF, pinned); Theorem 1.1 and Section 1.1, p. 2. Unrefereed. Library home: OpenAI 2026; result page Theorem 1.1.
KuWa26: Kuang, P. and Wang, Y., An optimal bound for Ramsey goodness of cycles. arXiv:2607.26956 (v1 29 July 2026; v2 31 August 2026). Preprint; abstract only. Lead, recorded below.
Ma20: Madarasi, P., The Ramsey number of a long cycle and complete graphs. arXiv:2003.12691 (v2 25 September 2020). Abstract only. Lead, recorded below.

Problem 551

Status

Proof claims

Discussion