第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}

個あることを示せ。

ステップ 1/5: グラフの次数を定める

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

詳しい解説

$1,\ldots,n$ を頂点、 $S$ の組を辺とみなす。頂点 $i$ の隣接集合を $D_i$ 、その大きさを $d_i=|D_i|$ とする。各辺には端点が2つあるので $\sum_{i=1}^n d_i=2m$ 。