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 2 of 5: Lower-bound common neighbors of each edge

Previous step Next step

|D_i\cap D_j|\ge d_i+d_j-n\qquad((i,j)\in S)

Detailed analysis

For an edge $(i,j)$ , a vertex in $D_i\cap D_j$ forms a good triple with $i,j$ . Both neighbor sets lie among the $n$ vertices, so inclusion–exclusion gives $|D_i\cap D_j|=d_i+d_j-|D_i\cup D_j|\ge d_i+d_j-n$ .