2
$\begingroup$

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.

$\endgroup$
4
  • 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

6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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