Edges at a vertex of K₆
5
Five neighbours.
The Ramsey number : in any red/blue colouring of the edges of there is a monochromatic triangle, while can be coloured with none.
This page is easier if you are comfortable with:
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.
Ramsey numbers show that in any large enough system some orderly pattern must appear.
Five edges force three of one colour, which closes a triangle.
These examples are worked by hand, step by step, so you can compare your own working.
In , how many edges meet a vertex, and how many must share a colour?
How many triangles does have?
In the pentagon/pentagram colouring of , how many edges are red?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
5
Five neighbours.
at least ⌈5/2⌉ = 3
Pigeonhole.
C(6, 3) = 20
Possible triples.
5 red + 5 blue edges
No monochromatic triangle.
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.
How many edges meet one vertex of K₆?
Two colours, 5 edges. How many must share a colour?
How many triangles does K₆ contain?
Total edges of K₅ and how many are red in the pentagon colouring?
K₅ is enough ✗
R(3,3) = 6 ✓
K₅ has a good colouring.
any triangle ✗
monochromatic only ✓
All three edges the same colour.
R(5,5) known ✗
only bounds known ✓
Ramsey numbers grow fast.
K₆ has 6 edges ✗
K₆ has 15 edges ✓
C(6, 2).
Try each one on paper, then open the answer. Use the solver above to see the full working.
15
21
10
35
4
9
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
6.
Pigeonhole at one vertex, then a case check.
Yes, pentagon red and diagonals blue.
15.
first moment method.
Turán’s theorem.
More in Discrete maths and number theory and the formula sheets.