Let $G = \left\langle {V,E} \right\rangle$, a simple and complete graph with the size of $n$.

Each edge in the graph can be colored with blue or red.
A "bad" triangle defined to be a triangle (circle with three edges) such that it contains two colors (two blue edges and one red and vice-verca).

Also, $d_i$ is the number for blue edges for the vertex $i$.

It appears that the number of bad triangles defined by the following formula which I'm trying to understand:

$$\sum\limits_{i = 1}^n {\frac{{({d_i} \cdot (n - 1 - {d_i}))}}{2}} $$

Trying to interpret it:
for each vertex, the number of bad triangles is the number of blue edges multiplied by the number of red edges divided by $2$.

But what is standing behind this?


Since the graph is complete, all edges are present. Thus, if we find a red and a blue edge with endpoints at a vertex $A$, we know the triangle with those two edges and the third edge joining them must have at least two colors. For every vertex, we can calculate the number of bad triangles found in this way by multiplying the number of red and blue edges of the vertex. We count every triangle twice now, because every bad triangle has two points where two edges of different color meet. Therefore, we need to divide the number of bad triangles we found by two, yielding $$ \frac 12 \sum_{v\in V}d_v(n-1-d_v)=\sum_{i=1}^n\frac{d_i(n-1-d_i)}2 $$ (We take $n-1-d_i$ instead of $n-d_i$, because there are $n-1$ points different from $v\in V$, and thus also $n-1$ edges joining $v$.)

Every pair of one blue and one red edge joining at a vertex can make exactly one bad triangle, because we can just join the endpoints of those two edges. We can choose one blue edge in $d_i$ ways. We can choose one red edge in $n-1-d_i$ ways. Together, this gives $d_i(n-1-d_i)$ ways to choose one blue and one red edge.

  • $\begingroup$ Can you make it more clear, why the multiplication of red colored edges and blue colored edges gives us the number of bad triangles? $\endgroup$ – AndrePoole Feb 6 '14 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.