Ramsey Number Explained with Worked Examples

The Ramsey number : in any red/blue colouring of the edges of there is a monochromatic triangle, while can be coloured with none.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Ramsey number means

Pick a vertex of ; it has 5 edges, so by the pigeonhole principle at least 3 have the same colour, say red, to vertices . If any of is red, it forms a red triangle with the chosen vertex; otherwise is a blue triangle. So 6 vertices always suffice. For , colour the pentagon edges red and the diagonals blue: the red graph and the blue graph are both 5-cycles, which contain no triangles, so .

The counting: has triangles and 15 edges (edges in a complete graph). Each vertex has degree 5, forcing at least edges of one colour. In a random colouring, the expected number of monochromatic triangles is (the first moment method), consistent with the theorem that at least one always exists.

Ramsey theory says complete disorder is impossible: large enough structures contain order. Other values are far harder: , while is only known to lie between 43 and 46. A related extremal result on edges is Turán's theorem, and the proof ideas use graph colouring language.

What is it used for?

Ramsey numbers show that in any large enough system some orderly pattern must appear.

How to use ramsey number

  1. Colour the edges of with two colours.
  2. Look for a monochromatic triangle.
  3. For use the pigeonhole argument at one vertex.
  4. For exhibit the pentagon colouring with none.

Graph

Counts for K6: edges at a vertex, forced same colour, trianglesedges at a vertex: 5same colour: at least 3triangles: 2000.511.522.533.5405101520Counts for K6: edges at a vertex, forced same colour, trianglescountyGraph with x from 0 to 4 and y from 0 to 22. Shows bars (3); point edges at a vertex: 5 at (1, 5); point same colour: at least 3 at (2, 3); point triangles: 20 at (3, 20).

Five edges force three of one colour, which closes a triangle.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: edges at a vertex

In , how many edges meet a vertex, and how many must share a colour?

Worked example
Answer
5, 35,\ 3
  1. Edges
  2. At least

Example 2: triangles in K₆

How many triangles does have?

Worked example
Answer
2020
  1. Formula

Example 3: colouring K₅

In the pentagon/pentagram colouring of , how many edges are red?

Worked example
Answer
5 (and 5 blue, no triangle)5\ \text{(and 5 blue, no triangle)}
  1. Pentagon edges

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Edges at a vertex of K₆

5

Five neighbours.

Same colour

at least ⌈5/2⌉ = 3

Pigeonhole.

Triangles in K₆

C(6, 3) = 20

Possible triples.

K₅ colouring

5 red + 5 blue edges

No monochromatic triangle.

Word problems

R(3, 3) = 6: every red/blue colouring of the edges of K₆ contains a monochromatic triangle, while K₅ can be coloured without one (pentagon red, diagonals blue). At a vertex of K₆, pigeonhole gives three edges of one colour.

Edges at a vertex

How many edges meet one vertex of K₆?

  1. 6 − 1
  2. Check: ✓5.

Pigeonhole

Two colours, 5 edges. How many must share a colour?

  1. ⌈5/2⌉
  2. Check: ✓3.

Count triangles Higher

How many triangles does K₆ contain?

  1. C(6, 3)
  2. Check: ✓20.

The K₅ colouring Higher

Total edges of K₅ and how many are red in the pentagon colouring?

  1. C(5, 2)10
  2. Red5
  3. Check: 5 red + 5 blue ✓10 edges, 5 red.

Common mistakes

R(3,3) = 5

K₅ is enough ✗

R(3,3) = 6 ✓

K₅ has a good colouring.

Counting two-colour triangles

any triangle ✗

monochromatic only ✓

All three edges the same colour.

Assuming easy computation

R(5,5) known ✗

only bounds known ✓

Ramsey numbers grow fast.

Confusing vertices and edges

K₆ has 6 edges ✗

K₆ has 15 edges ✓

C(6, 2).

Exam tips

  1. Fix a vertex.
  2. Pigeonhole on its edges.
  3. R(3,3) = 6.
  4. K₅ is the counterexample.
  5. Edges of K_n: C(n, 2).

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Edges of K₆ Foundation

15

2. Edges of K₇ Foundation

21

3. Triangles in K₅ Foundation

10

4. Triangles in K₇ Higher

35

5. ⌈7/2⌉ Higher

4

6. Edges at a vertex of K₁₀ Higher

9

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Ramsey number R(s, t)
Smallest n forcing a red K_s or blue K_t.
Monochromatic
All one colour.
Complete graph (K_n)
Every pair joined.
Pigeonhole principle
Distribution forces repeats.
Colouring
Assignment of colours to edges.
Clique
Complete subgraph.

Frequently asked questions

What is R(3, 3)?

6.

Why does K₆ force a monochromatic triangle?

Pigeonhole at one vertex, then a case check.

Is there a bad colouring of K₅?

Yes, pentagon red and diagonals blue.

How many edges has K₆?

15.

Which page covers the first moment method?

first moment method.

Which page covers Turán’s theorem?

Turán’s theorem.

More in Discrete maths and number theory and the formula sheets.