Problem
COM-B2-M06-P008 The Exact Value of \(R(3,3)\)
#8
★★★☆☆ Level 3 of 5
Using the upper bound for \(K_6\) and a colouring of \(K_5\), prove that \(R(3,3)=6\).
You need to prove two parts: \(6\) is enough and \(5\) is not enough.
The \(K_6\) result shows that with \(6\) vertices a monochromatic triangle is unavoidable, so \(R(3,3)\le6\).
On the other hand, colour \(K_5\) as follows: the sides of a pentagon are red and the diagonals are blue. Each colour forms a cycle of length \(5\), so there is no monochromatic triangle. Hence \(R(3,3)>5\).
Therefore \(R(3,3)=6\).
This introduces the culture of upper and lower bounds.