# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/RamseyNumbers.lean), 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](https://doi.org/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](https://doi.org/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](https://arxiv.org/abs/1703.08768)
4. V. Angeltveit and B. D. McKay, "R(5,5) ≤ 46" (2024; *Journal of Graph Theory*, 2026). [arXiv:2409.15709](https://arxiv.org/abs/2409.15709)
5. S. P. Radziszowski, "Small Ramsey numbers", *Electronic Journal of Combinatorics*, Dynamic Survey DS1, revision 18 (2026). [doi:10.37236/21](https://doi.org/10.37236/21)

## Source

Imported from [Small Ramsey Numbers (Radziszowski, dynamic survey DS1), Table Ia](https://www.combinatorics.org/ds1), 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.