Key takeaways
- The Ramsey number R(s, t) is the smallest n such that any red–blue colouring of the edges of Kₙ contains a red Kₛ or a blue Kₜ.
- R(3, 3) = 6: in any group of six people, three know each other or three are mutual strangers, and five people are not enough.
- The proof is a pigeonhole argument: one person's five relationships include three of the same kind, and those three people force a triangle.
- Ramsey's theorem guarantees every R(s, t) exists, with the bound R(s, t) ≤ R(s − 1, t) + R(s, t − 1).
- Exact values are known only for small cases: R(4, 4) = 18, while R(5, 5) is known only to lie between 43 and 46.
Take any six people. Either three of them all know each other, or three of them are all strangers to each other. Always. With five people this can fail. That fact, written R(3, 3) = 6, is the opening example of Ramsey theory, the part of combinatorics whose theme, loosely put, is that any large enough structure contains an orderly piece.
The party problem in graph form
MathWorld describes the Ramsey number R(s, t) as the solution to the party problem: the minimum number of guests that must be invited so that at least s will know each other or at least t will not know each other.
In graph language, make each guest a vertex of the complete graph Kₙ and colour each edge red if the pair know each other and blue if not. Then R(s, t) is the smallest n such that every red–blue colouring of Kₙ's edges contains a red Kₛ or a blue Kₜ. (MathWorld phrases the same thing with cliques and independent sets.)
Why six people are enough
Claim. Every red–blue colouring of K₆ contains a red triangle or a blue triangle.
Proof. Pick any vertex v. It has 5 edges, each red or blue. By the pigeonhole principle, at least ⌈5/2⌉ = 3 of them have the same colour; say v is joined by red edges to x, y and z. (If the three are blue, swap the colours throughout.)
Now look at the three edges xy, yz and xz.
- If any of them is red, say xy, then v, x and y form a red triangle.
- If none of them is red, all three are blue, and x, y and z form a blue triangle.
Either way there is a single-coloured triangle. ∎
The proof is short, but notice how much it uses: a pigeonhole step to find three edges of the same colour, then a case split that forces a triangle in one colour or the other.
Why five people are not enough
To show R(3, 3) > 5, it is enough to give one colouring of K₅ with no single-coloured triangle. Place five vertices as a regular pentagon. Colour the five sides red and the five diagonals blue.
- The red edges form a 5-cycle, which contains no triangle.
- The blue edges form a five-pointed star, which is also a 5-cycle, with no triangle.
So five guests can avoid both three mutual friends and three mutual strangers, and R(3, 3) = 6 exactly. The Wikipedia article on Ramsey's theorem notes that a lower bound usually requires exhibiting a colouring like this one, called a Ramsey graph; the upper bound needed an argument, which is where techniques such as proof by contradiction come in.
Ramsey's theorem: the numbers always exist
Ramsey's theorem says R(s, t) is finite for every s and t: however large the patterns you want to force, some finite party size guarantees one. MathWorld states the theorem; the standard proof also gives an upper bound,
R(s, t) ≤ R(s − 1, t) + R(s, t − 1).
The idea copies the R(3, 3) proof: pick a vertex v in a graph with R(s − 1, t) + R(s, t − 1) vertices. It has one fewer neighbour than that total, so either it has at least R(s − 1, t) red neighbours or at least R(s, t − 1) blue ones. In the first case, the red neighbours contain a blue Kₜ, finishing the proof, or a red Kₛ₋₁, which together with v makes a red Kₛ. The second case is symmetric.
Starting from R(2, t) = t (any red edge is a red K₂, otherwise all t vertices are joined in blue), the bound gives R(3, 3) ≤ 3 + 3 = 6, which happens to be exact, and R(3, 4) ≤ R(2, 4) + R(3, 3) = 4 + 6 = 10. The true value is 9: the Wikipedia article on Ramsey's theorem shows how the handshake lemma trims the bound to 9 when both terms are even.
What is known
| Ramsey number | Value |
|---|---|
| R(3, 3) | 6 |
| R(3, 4) | 9 |
| R(4, 4) | 18 |
| R(4, 5) | 25 |
| R(5, 5) | Between 43 and 46 |
R(4, 4) = 18 combines both kinds of argument: the recursive bound gives R(4, 4) ≤ R(3, 4) + R(4, 3) = 18, and the Paley graph on 17 vertices gives a colouring of K₁₇ with no single-coloured K₄, so 17 guests are not enough. The bounds on R(5, 5) come from a colouring of K₄₂ found by Geoffrey Exoo in 1989 and an upper bound of 46 proved by Vigleik Angeltveit and Brendan McKay in 2024. Stanisław Radziszowski's dynamic survey "Small Ramsey Numbers" in The Electronic Journal of Combinatorics is the reference that tracks the current values and bounds.
Why the numbers are so hard
To verify R(5, 5) = 43 by brute force you would need to check that every colouring of K₄₃ contains a single-coloured K₅. K₄₃ has 903 edges, so there are 2⁹⁰³ colourings, a number with 272 digits. Clever search can prune most of them, but the growth is so fast that exact values stop at very small sizes. Joel Spencer records Paul Erdős's joke about it: if an alien force demanded the value of R(5, 5) on pain of destroying the Earth, we should marshal all our computers and mathematicians to find it; if they demanded R(6, 6), we should try to destroy the aliens instead.
Where Ramsey ideas appear
Edge colourings like these are a cousin of the vertex colourings in graph colouring, and the method is the one used throughout this article: count, apply pigeonhole, and force a structure.
Discrete Math: Study & Quiz has units on combinatorics and graph theory, with lessons and knowledge checks. It is one of our education apps, and the discrete math hub collects the series, starting from graph theory basics.
Good to know
Frequently asked questions
What is a Ramsey number?
Why is R(3, 3) = 6?
Why are Ramsey numbers so hard to compute?
What is known about R(5, 5)?
Sources
- Ramsey Number (opens in a new tab)Wolfram MathWorld — accessed
- Small Ramsey Numbers (Stanisław Radziszowski), Dynamic Survey DS1 (opens in a new tab)The Electronic Journal of Combinatorics — accessed
- Ramsey's theorem (opens in a new tab)Wikipedia — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.