Problem 4

Let

S

be a set consisting of

m

pairs

(a,b)

of positive integers with

1\le a<b\le n

. Show that there are at least

\dfrac{m(4m-n^2)}{3n}

triples

(a,b,c)

such that

(a,b),(a,c)

, and

(b,c)

belong to

S

Step 3 of 5: Sum over edges and account for triple multiplicity

Previous step Next step

T\ge\frac13\sum_{(i,j)\in S}(d_i+d_j-n)=\frac13\left(\sum_{i=1}^n d_i^2-mn\right)

Detailed analysis

Summing the common-neighbor bound over all $m$ edges gives the number of incidences of an edge with a completing vertex. Every good triple has three edges, so it is counted three times. Also, each $d_i$ occurs once for every incident edge, hence the sum of the degree terms is $\sum_i d_i^2$ and the $n$ term contributes $mn$ .