Exercise 1810Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Monochromatic triangle

#pigeonhole#Ramsey#monochromatic

Statement

Color each edge of $K_6$ red or blue. Show that there is a monochromatic triangle.

Hint

Fix a vertex $v$ . Among its $5$ edges, at least $3$ are the same color (pigeonhole).

Show solutionHide solution

Pigeonhole at one vertex. Vertex $v$ has $5$ edges, each red or blue: at least $3$ are red (WLOG). Say $vA$ , $vB$ , $vC$ are red.

Check $AB$ , $BC$ , $CA$ .
- If any, say $AB$ , is red: $\triangle vAB$ is red. Done.
- If none is red: $\triangle ABC$ is all blue. Done.

Conclusion. $K_6$ has a monochromatic triangle. (Ramsey $R(3,3)\le6$ .)