# Red-blue coloring of the complete graph $K_n$​ such that there are more red edges than blue edges, and there is no red triangle.

Let us prove that for every $$n>1$$ there exists a $$2$$-coloring of a complete graph $$K_n$$ red and blue, where there are more red edges than blue and there is no monochromatic red triangle, where all the edges are red.

I thought of the pigeonhole principle, because a triangle is basically a $$K_3$$

For $$K_5$$ there exists, for less than $$5$$ it is trivial. I tried making cycles, and using these circles to make the coloring.

• What have you tried? Can you construct an example for some non-trivial but still small enough $n$ (like $n = 5, 6$)? $\quad$ What's a good way to guarantee that there are no monochromatic red triangles (or even a larger class of graphs)? Commented Dec 28, 2023 at 18:23
• What are your thoughts? What have you tried? Where are you stuck? Commented Dec 28, 2023 at 18:23
• Note, you are not talking about a 2-coloring, but about a 2-edge coloring. Commented Jan 4 at 12:09
• What about my answer do you not get? I'm happy to help. There's no need to put the question on bounty... Commented Jan 4 at 14:38

A slight re-translation of the question asks that you find a class of graphs with $$>\binom{n}{2}/2 = \frac{n(n-1)}{4}$$ edges with no triangles. Hint: what is the maximal number of edges in a triangle-free graph and what are the extremal examples? If you are coming in without any knowledge of extremal graph theory, this theorem is called Mantel's theorem.