total number of triangles in $G$ and $G^C$

Question

Prove that if G is a simple k-regular graph on n vertices then the total number of triangles in $G$ and $G^C$ is :
$n\choose 3$-$nk(n-k-1)/2$.
I can understand how $n\choose 3$ comes but doesn't it give the total number of triangles in $G$ and $G^C$?

I don't understand how to obtain $nk(n-k-1)/2$.
Can someone please help me with this

Answer 1

There are easy examples to show that the number of triangles in $G$ and $G^C$ can be less than $\binom{n}3$. For example, let $G=C_4$, the $4$-cycle: $G^C$ is the disjoint union of two copies of $K_2$, so neither $G$ nor $G^C$ contains any triangle, yet $\binom43=4$, not $0$. $\binom{n}3$ is simply the maximum possible number of triangles in $G$ and $G^C$.

To get the actual total number of triangles in $G$ and $G^C$, we need to count the triangles in $K_n$ that are not in $G$ and not in $G^C$. Let $u$ be any vertex; $\deg_Gu=k$, and $\deg_{G^C}u=n-k-1$. Thus, there are $k(n-k-1)$ ways to choose two edges incident at $u$ in such a way that one of them is in $G$ and the other in $G^C$. We can do this for each of the $n$ vertices, so as a first approximation we count $nk(n-k-1)$ triangles in $K_n$ that aren’t in $G$ or in $G^C$. However, we’ve counted every one of these triangles twice, so the actual number of such triangles is only $$\frac{nk(n-k-1)}2\;,$$ meaning that $G$ and $G^C$ between them really do contain $$\binom{n}3-\frac{nk(n-k-1)}2$$ triangles.

The spoiler-protected block below contains a proof that each of these ‘bad’ triangles is counted exactly twice, but you should try to find one for yourself before looking.

To see why this is so, say that vertices $u,v$, and $w$ form a triangle that is in neither $G$ nor $G^C$. Then two of the edges $uv,uw$, and $vw$ must be in one of the complementary graphs $G$ and $G^C$, while the remaining edge is in the other. Without loss of generality suppose that $uv$ and $uw$ are in one of graphs, while $vw$ is in the other. Then this triangle got counted once at vertex $v$, when we chose edges $vu$ and $vw$, and once again at vertex $w$, when we chose edges $wu$ and $wv$. Those are the only two vertices at which it was counted, and it was counted only once at each of those vertices, so it was counted exactly twice.