Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles?

Question

I am working on the following problem on 2-coloured complete graphs:

$K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and blue degree 5. Is this possible?

I am pretty sure the answer is 'no' but I am not sure how to explain my answer.

Any help would be greatly appreciated!

Answer 1

Hint. There are $9$ vertices; if every one of them had "red degree" $3$, then the graph containing only the red edges would contradict one of the most basic theorems of graph theory.

Answer 2

Hint:

• Take bicolored $K_9$.
• Observe that there exists a vertex of even blue degree and name it $u$.
• Set $B$ and $R$ to be respectively the blue and red neighbors of $u$; observe that $|B| \geq 5$ or $|R| \geq 4$.
• Strenghten that to $|B| \geq 6$ or $|R| \geq 4$.
• Bicolored $K_6$ will always have either blue or red triangle.
• Bicolored $K_4$ is either all blue or it has at least one red edge.

I hope this helps $\ddot\smile$