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 1 of 5: Build the graph degrees

Previous step Next step

D_i=\{j:(i,j)\in S\text{ or }(j,i)\in S\},\qquad d_i=|D_i|

Detailed analysis

Regard $1,\ldots,n$ as vertices and the pairs in $S$ as edges. Let $D_i$ be the neighbor set of vertex $i$ and $d_i=|D_i|$ . Since an edge has two endpoints, $\sum_{i=1}^n d_i=2m$ .