Exercise 1697Combinatorics › Graph theoryL1Added 3 Nov 2026

Ramsey numbers

#Ramsey#R(3#3)#coloring

Statement

Compute $R(3,3)$ , the smallest $n$ such that any 2-coloring of $K_n$ has a monochromatic triangle.

Hint

$R(3,3)=6$ : any 2-coloring of $K_6$ has a monochromatic triangle, but $K_5$ can be colored without one.

Show solutionHide solution

Solution

Upper bound. In $K_6$ , fix a vertex: at least $\lceil5/2\rceil=3$ edges to it are the same color. Then use the pigeonhole argument from the "Monochromatic triangle" exercise.

Lower bound. A 5-cycle with all long diagonals in one color, the cycle edges in the other, avoids monochromatic triangles.

Conclusion. $R(3,3)=6$ .

Ramsey numbers

Statement

Solution

More problems in Graph theory