The Ramsey number R(5,5)

What is the least $n$ such that every red-blue colouring of the edges of the complete graph $K_n$ contains five vertices joined only by edges of one colour? This number, $R(5,5)$, is known to lie between 43 and 46. A colouring of $K_{43}$ with no single-coloured $K_5$ would be checked in seconds; a better upper bound needs a large but repeatable computation.

Problem

The Ramsey number $R(k, l)$ is the least $n$ such that every graph on $n$ vertices contains a clique of size $k$ or an independent set of size $l$; equivalently, every 2-colouring of the edges of $K_n$ contains a red $K_k$ or a blue $K_l$. Ramsey's theorem guarantees that these numbers are finite.

Task: determine $R(5,5)$. It is known that $43 \le R(5,5) \le 46$.

Background

Exact values are known for only a few small parameters: $R(3,3) = 6$ is a classical exercise, Greenwood and Gleason found $R(3,4) = 9$, $R(3,5) = 14$ and $R(4,4) = 18$ in 1955, and McKay and Radziszowski proved $R(4,5) = 25$ in 1995. $R(5,5)$ is the smallest open diagonal case. Lower bounds come from explicit colourings, usually found by computer search; upper bounds require ruling out every colouring of a given size, which for $R(5,5)$ has meant combining counting identities, linear programming and very large case analyses. A value of 50 that circulates online is wrong, as the survey notes.

What is known

• Lower bound $R(5,5) \ge 43$: Exoo (1989) gave a 2-colouring of $K_{42}$ with no monochromatic $K_5$.
• Upper bounds: $49$ (McKay and Radziszowski, 1997); $48$ (Angeltveit and McKay, 2018); $46$ (Angeltveit and McKay, posted 2024, published in the Journal of Graph Theory), by linear programming together with a large number of cases checked by computer, each computation implemented independently by both authors.
• Conjecture: McKay and Radziszowski (1997) gave strong evidence that $R(5,5) = 43$ and that there are exactly 656 colourings of $K_{42}$ without a monochromatic $K_5$, up to isomorphism.

What would count as progress

• A 2-colouring of $K_{43}$ with no monochromatic $K_5$, which would show $R(5,5) \ge 44$ and refute the conjecture. Checking it means testing the $\binom{43}{5} = 962{,}598$ five-vertex subsets, a matter of seconds.
• A proof that $R(5,5) \le 45$, with the linear programs and case enumerations published so that they can be rerun independently.
• New structural information about extremal colourings, for example a complete enumeration of the colourings of $K_{42}$ without a monochromatic $K_5$.
• The problem is stated in Lean in formal-conjectures, with the bounds $43 \le R(5,5) \le 46$.

References

1. G. Exoo, "A lower bound for R(5,5)", Journal of Graph Theory 13 (1989), 97–98. doi:10.1002/jgt.3190130113
2. B. D. McKay and S. P. Radziszowski, "Subgraph counting identities and Ramsey numbers", Journal of Combinatorial Theory, Series B 69 (1997), 193–209. doi:10.1006/jctb.1996.1741
3. V. Angeltveit and B. D. McKay, "R(5,5) ≤ 48", Journal of Graph Theory 89 (2018), 5–13. arXiv:1703.08768
4. V. Angeltveit and B. D. McKay, "R(5,5) ≤ 46" (2024; Journal of Graph Theory, 2026). arXiv:2409.15709
5. S. P. Radziszowski, "Small Ramsey numbers", Electronic Journal of Combinatorics, Dynamic Survey DS1, revision 18 (2026). doi:10.37236/21

Source

Imported from Small Ramsey Numbers (Radziszowski, dynamic survey DS1), Table Ia, curated by Stanisław Radziszowski. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.