Open problem, Combinatorics and discrete mathematics, posed 1930

Value of the Ramsey number R(5,5)

Open

Determine the exact diagonal Ramsey number $R(5, 5)$ : the smallest positive integer $n$ such that every $2$ -coloring of the edges of the complete graph $K_n$ contains a monochromatic copy of $K_5$ (equivalently, every simple graph on $n$ vertices contains either a clique of size $5$ or an independent set of size $5$ ).

Research frontier as of 2026

As of 2026, the best known bounds are $43 \le R(5, 5) \le 46$ . The lower bound $43$ comes from $656$ known $(5, 5, 42)$ -graphs (all sharing the same $328$ graphs and their complements), and because exhaustive heuristic searches have never found a $(5, 5, 43)$ -graph, McKay and Radziszowski conjectured that $R(5, 5) = 43$ . The upper bound $R(5, 5) \le 46$ is due to Angeltveit and McKay (2024 preprint), who combined linear programming on edge-triangle-quadruple densities with a massive parallel extension of $(4, 5, k)$ -subgraphs.

Best known results

The exact value satisfies $43 \le R(5, 5) \le 46$ (Exoo 1989 for the lower bound; Angeltveit and McKay 2024 preprint for the upper bound).
Exactly $350,904$ non-isomorphic $(4, 5, 24)$ -graphs exist, and their neighborhood gluing rules constrain any hypothetical $(5, 5, n)$ -graph for $n \ge 43$ .

Tools and where they stop

Tool	Achieved	Where it stops
Subgraph-density linear programming and neighborhood extension (McKay–Radziszowski, Angeltveit–McKay)	Uses the fact that the neighborhood and non-neighborhood of any vertex in a $(5, 5, n)$ -graph must be $(4, 5, d)$ and $(5, 4, n - 1 - d)$ graphs to eliminate $n = 49, 48, 47$ .	As $n$ approaches $43$ , vertex degrees $d$ fall in the range $19 \le d \le 22$ where the catalog of $(4, 5, d)$ -graphs explodes into trillions of isomorphism types.

Open questions

Is $R(5, 5) = 43$ , as conjectured by McKay and Radziszowski?
Are the $656$ known $(5, 5, 42)$ -graphs the complete set of all extremal $42$ -vertex graphs avoiding monochromatic $K_5$ ?

References

Geoffrey Exoo (1989). A lower bound for r(5, 5) · DOI:10.1002/jgt.3190130113
Brendan D. McKay, Stanisław P. Radziszowski (1997). Subgraph counting identities and Ramsey numbers · DOI:10.1006/jctb.1996.1741
Vigleik Angeltveit, Brendan D. McKay (2024). R(5,5) <= 46 · arXiv:2409.15709 [preprint, not peer-reviewed]