第4問

S

を、

1\le a<b\le n

を満たす正整数の組

(a,b)

を

m

個含む集合とする。

(a,b),(a,c)

、および

(b,c)

が

S

に属する三つ組

(a,b,c)

が少なくとも

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

個あることを示せ。

ステップ 2/5: 各辺の共通隣接点を下から評価する

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

詳しい解説

辺 $(i,j)$ に対し、 $D_i\cap D_j$ の頂点は $i,j$ と良い三つ組を作る。二つの隣接集合は $n$ 頂点内にあるので、包除原理から $|D_i\cap D_j|=d_i+d_j-|D_i\cup D_j|\ge d_i+d_j-n$ 。