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.

  • 1
    $\begingroup$ 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)? $\endgroup$
    – Calvin Lin
    Commented Dec 28, 2023 at 18:23
  • $\begingroup$ What are your thoughts? What have you tried? Where are you stuck? $\endgroup$ Commented Dec 28, 2023 at 18:23
  • $\begingroup$ Note, you are not talking about a 2-coloring, but about a 2-edge coloring. $\endgroup$ Commented Jan 4 at 12:09
  • $\begingroup$ What about my answer do you not get? I'm happy to help. There's no need to put the question on bounty... $\endgroup$
    – koifish
    Commented Jan 4 at 14:38

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .