Lower bound for monochromatic triangles in $K_n$

Say $K_n$ is a complete graph of $n$ nodes, and every edge is either blue or red. I'm trying to find $T_n$, which is the lower bound for the number of monochromatic triangles in $K_n$ (monochromatic meaning triangles whose 3 edges are of the same color).

I'm trying this approaches:

A. Let $v_i$ a vertex in $K_n$. This vertex belongs to $\binom{n-1}{2} $ different triangles. Let $r$ be the number of red edges that $v_i$ belongs $b$ the number of blue edges. Of course, $$r + b = n-1$$ So, the number of non-monochromatic (dual/stereo-chromatic?) triangles is $r \cdot b$, and so our bound would be (for vertex $V_i$)

$$T_n \le \binom{n-1}{2} - r \cdot b$$

Question is - how do I know when $r \cdot b$ is the maximal possible number? Also, this would give me the upper bound, how do I find the lower bound?

Thanks in advance!

Solution 1:

Here's a proof, from Wikipedia, that $K_6$ has at least 2 monochromatic triangles. You may find that this method of proof generalizes to give you the lower bound you want.

"An alternate proof works by double counting. It goes as follows: Count the number of ordered triples of vertices $x, y, z$ such that the edge $(xy)$ is red and the edge $(yz)$ is blue. Firstly, any given vertex will be the middle of either $0\times5=0$ (all edges from the vertex are the same color), $1\times4=4$ (four are the same color, one is the other color), or $2\times3=6$ (three are the same color, two are the other color) such triples. Therefore there are at most $6\times6=36$ such triples. Secondly, for any non-monochromatic triangle $(xyz)$, there exist precisely two such triples. Therefore there are at most 18 non-monochromatic triangles. Therefore at least 2 of the 20 triangles in the $K_6$ are monochromatic."

On the other hand, if you want all the work done for you, there is an answer in A W Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959) 778-783, also in Frank Harary, The two-triangle case of the acquaintance graph, Math. Mag. 45 (1972) 130-135.