counting triangles in a graph or its complement

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.

Solution 1:

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.