Problem
COM-B2-M06-P009 If There Are No Triangles
#9
★★★☆☆ Level 3 of 5
The edges of \(K_n\) are coloured red and blue, and there are no monochromatic triangles. Prove that \(n\le5\).
Prove that from each vertex there are at most two red edges and at most two blue edges.
Take a vertex \(v\). If three red edges leave it to \(a,b,c\), then no edge among \(a,b,c\) can be red, otherwise there is a red triangle with \(v\). Hence all edges among \(a,b,c\) are blue, giving a blue triangle. Contradiction.
Thus the red degree of every vertex is at most \(2\). Similarly, the blue degree is at most \(2\). But \(n-1\) edges leave a vertex, so \(n-1\le4\), hence \(n\le5\).
An alternative proof of the upper bound \(R(3,3)\le6\).