Given a simple graph $G$ [no loops or parallel edges] on six vertices,
let $G^c$ denote its complement.
It is known that either $G$ or $G^c$ must contain a triangle
$T$ in it. [An example of a Ramsey number I think.]
My question came up when I tried to find such a graph on six vertices
which had only one $T$ in it or its complement.
I believe if I did things right there are none of these.
This I tried to check by drawing a copy of each graph $G$
on six vertices which has a $T$ in it,
and then looking at the complements to see if any had
no $T$'s in them. I found none.
One way to pose my question for a general number $n$ of vertices
is then as follows: Consider the set
of all graphs $G$ on $n$ vertices,
and for each one construct $G^c.$
Count the number of $T$ in $G$ and
add that to the number of $T$ in $G^c.$
Finally find the minimal such sum for the given $n$
and call that say $M(n).$ So my above six vertex conjecture
is that $M(6)=2.$
By considering a cycle graph on five vertices
we find $M(5)=0.$
So going further one could ask if anything is known
about this minimum function $M(n)$ for larger $n$
[such as bounds, etc.] And does it have a name?
I would also like to see a simpler way to handle the six vertex case,
one not involving drawing all the graphs.
Best Answer
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: