---
tag: 00TQV3F5S4
kind: statement
role: theorem
name: Ramsey's theorem
msc: [05D10, 05C55]
uses: [03WKB2H474, 0G52BPNPKG]
sources:
  - url: https://en.wikipedia.org/wiki/Ramsey's_theorem
    locator: lead section
same_as:
  wikidata: Q918099
  wikipedia: Ramsey's theorem
---

## Statement

Let $r$ and $s$ be positive integers.
Then there is a positive integer $n$ with this property.
Colour each edge of the [[complete graph|03WKB2H474]] $K_n$ blue or red, in any way.
Then there is a blue [[clique|0G52BPNPKG]] with $r$ vertices or a red clique with $s$ vertices.

## Remarks

The least such $n$ is the [[Ramsey number|01DSVCRF6X]] $R(r, s)$.
The proof gives the bound $R(r, s) \le R(r - 1, s) + R(r, s - 1)$, by induction on $r + s$.
The theorem also holds for any finite number of colours.

## History

Frank Ramsey proved the first version of the theorem in a 1930 paper on formal logic.
This result started the field now called Ramsey theory.

## Explanations

### L1 human

Complete disorder is impossible in a large enough structure.
If you colour the edges of a large complete graph with two colours, a large clique of one colour always appears.