Find the smallest $n$ such that a two colouring $n$ edges of $K_9$ will always produce monochromatic triangle.

Question

Let $K_9$ be the complete $9$ vertex graph. Each edge can be coloured red, blue or left uncoloured. Find the smallest $n$ such that when $n$ edges are coloured, there necessarily must be a monochromatic triangle.

After going optimal algorithm, it seems $30$ seems to be the upper bound, and $31$ or more edges will always produce a monochromatic triangle. I'm not sure how to prove that is the case, but I suspect pigeonhole is used. Can anyone help me prove that $31$ or more edges guarantees a monochromatic triangle?

Answer 1

Lemma: Any two coloring of $K_6$ produces a monocromatic triangle.

Note: This does not hold necessery for $K_5$. Find an example.

So if we have a colored $G\simeq K_6$ then we are done. So if in $K_9$ there is no $G$ then we have by Turan's theorem:

$$\varepsilon \leq \Big[{2\cdot 9^2\over 5}\Big] =32$$

So if $K_9$ has at least $33$ colored edges there is colored $K_6$ and thus by lemma a conclusion.

Construction of nonexistence for $32$ edges is easy: Make 4 sets $A_1,A_2,A_3,A_4$ each with two vertices and $A_5$ with a single vertex.

Then connect all vertices between $A_i$ and $A_j$ with blue edges iff $|i-j|=1$ modulo $5$ and else with red edges. Edges in each $A_i$ are uncolored.