This proof considers the even-sized subsets of vertices of a pentagon. There are 16 such subsets: The empty set, the five sides of $P$, the five diagonals of $P$, and the five sets of size 4.
Each subset corresponds to a vertex in the graph we want to color.
The color of the edge between two vertices is found by considering the symmetric difference of their two subsets.
The symmetric difference operation $\triangle$ takes any two such subsets to a third.
If the subsets are different, the result cannot be empty, and so must be one of the other types: a side, a diagonal, or size 4.
The coloring strategy is simply to use one color for each of these three types.
Any triangle $\{a,b,c\}$ in the graph we are coloring consists of three edges, colored according to the type of $f(a) \triangle f(b)$, the type of $f(b) \triangle f(c)$, and the type of $f(a) \triangle f(c)$.
This is easy to reason about, because the identity
$$
\underbrace{(f(a) \triangle f(b))}_{\mbox{subset 1}} \; \triangle \;
\underbrace{(f(b) \triangle f(c))}_{\mbox{subset 2}} =
\underbrace{f(a) \triangle f(c)}_{\mbox{subset 3}}
$$
tells us that if there is a monochromatic triangle, then there must be two subsets of the same type whose symmetric difference is also of the same type.
But the symmetric difference of two sides is either a diagonal or of size 4, depending on whether the sides shared a vertex or not.
Similarly, the symmetric difference of two diagonals is either a side or of size 4, depending on whether the diagonals shared a vertex or not.
And finally, the symmetric difference of two distinct subsets of size 4 (so each subset is only missing a single vertex) has to be a subset of size 2 (namely the two missing vertices), and is thus either a side or a diagonal.
$\scriptsize\mbox{(You might wonder whether the final coloring of the graph is symmetric in all three colors, since it is clearly symmetric}$
$\scriptsize\mbox{in the first two (by rearranging the pentagon to make the diagonals be the sides), and surprisingly, the answer is yes!)}$
Suppose each edge of $K_n$ is colored red or blue. Let $r_i$ and $b_i$ denote the red degree and the blue degree of the vertex $v_i.$ Let $t$ denote the number of non-monochromatic triangles, i.e., triangles having at least one edge of each color. Let $a$ denote the number of $2$-colored angles, i.e., pairs $\{e,f\}$ where $e$ and $f$ are adjacent edges of different colors. Observe that
$$2t=a=\sum_{i=1}^nr_ib_i.\tag1$$
Case I. $n$ is even, say $n=2k.$
Then the sum (1) is maximized when $\{r_i,b_i\}=\{k,k-1\}$ for each $i,$ and in that case
$$t=\frac12\sum_{i=1}^{2k}k(k-1)=k^2(k-1),$$
and so the number of monochromatic triangles is
$$M(2k)=\binom{2k}3-k^2(k-1)=\frac{k(k-1)(k-2)}3.$$
Example. For $n=6$ the minimum number of monochromatic triangles is $2.$
Case II. $n=4k+1.$
The sum (1) is maximized when $r_i=b_i=2k$ for each $i,$ and in that case
$$t=\frac12\sum_{i=1}^{4k+1}(2k)^2=2k^2(4k+1),$$
and so the number of monochromatic triangles is
$$M(4k+1)=\binom{4k+1}3-2k^2(4k+1)=\frac{2k(k-1)(4k+1)}3.$$
Case III. $n=4k+3.$
It's not possible to have $r_i=b_i=2k+1$ for all $i,$ since $2k+1$ and $n=4k+3$ are both odd. The sum (1) is maximized when $r_i$ and $b_i$ are as nearly equal as possible, e.g., when $\{r_1,b_1\}=\{2k,2k+2\}$ and $r_i=b_i=2k+1$ for all $i\ne1.$ In that case
$$t=\frac12\left[(2k)(2k+2)+\sum_{k=2}^{4k+3}(2k+1)^2\right]=2k(k+1)+(2k+1)^3=8k^3+14k^2+8k+1,$$
and so the number of monochromatic triangles is
$$M(4k+3)=\binom{4k+3}3-(8k^3+14k^2+8k+1)=\frac{8k^3+6k^2-2k}3.$$
Construction of extremal graphs. In cases I and II we can take $G=C_n^{\lfloor n/4\rfloor}$ for the red graph. In case III we start with $C_{4k+3}^k$ and (with vertices numbered cyclically) add the $2k+1$ edges
$v_2v_{2k+3},\ v_3v_{2k+4},\dots,\ v_{2k+2}v_{4k+3}.$
References. The function $M(n)$ is OEIS sequence A014557; the general formula is
$$M(n)=\binom n3-\left\lfloor\frac n2\left\lfloor\left(\frac{n-1}2\right)^2\right\rfloor\right\rfloor;$$
the original reference is:
A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783.
Best Answer
We know that $N(3,4;2)=9$. By symmetry, we have that $N(4,3;2)=9$. Thus we have the following: $ \lbrack N(4,4;2)\leq N(3,4;2)+N(4,3;2)=18 \rbrack $
Thus we create a counterexample, $K_{17}$ that does not contain any red $K_{4}$ or green $K_{4}$. To do this, we label the vertices $v_{1}=1,\dots,v_{17}=17$. Then we take all edges, $(v_{i},v_{j})$ with $i-j\equiv\pm1,2,4\text{or}8$ to be red. First off, it is easy to show that the only 3 node closed paths that can be formed are by the vertices $T_{1}=\{v_{i},v_{i+1},v_{i+2}\}$ or $T_{2}=\{v_{i},v_{i+4},v_{i+8}\}$, or $T_{3}=\{v_{i},v_{i+2},v_{i+4}\}$ (i.e. sequences $i_{1},i_{2},i_{3}$ whose elements differ by $1,2,4,\text{or}8$), or some $T$ containing permutations of these nodes. Thus in order to form $K_{4}$ from one of these triangles, we must be able to find a vertex $v_{i_{4}}$ such that $v_{i_{4}}$ is connected to each $v_{i_{1}},\dots,v_{i_{3}}$(i.e. each 3-shuffle of any of the 4 vertices: $(v_{i_{j_{1}}},\dots v_{i_{j_{3}}})$ should contain a triangle, and thus $v_{i_{4}}$ such form a triangle with each of the other $v_{i_{j}}$. However, looking at the available triangles, we find that this is impossible. E.g. for $T_{1}$, adding a $v_{\ell}$ would not produce a triangle between $\{v_{i},v_{i+1},v_{\ell}\}$ for $\ell=i+4$, $i-4$, $i+8$, $i-8$. The same holds for $T_{2}$, $T_{3}$ for similar reasons.
Now we look at the set of green edges (the edges $(v_{i},v_{j})$ with $i-j\equiv3,5,6,7$). (note that we do not include $9$ because in this situation, a difference of $8$ is equivalent to a difference of $9$ by symmetry of the graph. We can only have the following triangles $T_{1}=\{v_{i},v_{i+3},v_{i+6}\}$, $T_{2}=\{v_{i-5},v_{i},v_{i+7}\}$ since $-12\bmod17=5$, and $T_{3}=\{v_{i-5},v_{i},v_{i+6}\}$ for similar reasons. However, by the same reasoning above, we cannot form $K_{4}$ from these triangles using the available vertices and edges. E.g. For $T_{1}$, we cannot add $v_{i-5}$ (because $\{v_{i-5},v_{i},v_{i+3}\}$ is not an available triangle) or $v_{i+5}$ or $v_{i-7}$ or $v_{i+7}$ for similar reasons. Thus we see that we cannot form a red or green $K_{4}$ in this counter example, so we have shown that \begin{eqnarray*} N(4,4;2) & \nless & 18\implies\\ N(4,4;2) & = & 18 \end{eqnarray*}