極値集合論の美しい２つの定理

• $n$ が偶数の場合
  頂点を $\dfrac{n}{2}$ ずつに分けてその間を全て辺で結んだグラフ（完全二部グラフ $K_{\frac{n}{2},\frac{n}{2}}$）を考える。このグラフには明らかに三角形がない。そして辺の数は $\dfrac{n^2}{4}$ である。

• $n$ が奇数の場合
  同様に $K_{\frac{n+1}{2},\frac{n-1}{2}}$ を考えればよい。

三角形を含まないグラフ $G=(V,E)$ について考える。頂点 $u$ から出ている辺の数を $d(u)$ と書く。

三角形がないという条件から，$(u,v)\in E$ のとき，他の任意の頂点 $w$ に対して $(u,w)\not\in E$ または $(v,w)\not\in E$ である。つまり，$d(u)+d(v)\leq n$

よって，

$\displaystyle\sum_{u\in V}d(u)^2=\sum_{(u,v)\in E}\{d(u)+d(v)\}\leq n|E|$

（真ん中の式では各 $d(u)$ が $d(u)$ 回足されているので $d(u)^2$ の和と等しい）

また，コーシー・シュワルツの不等式より，

$(1^2+\cdots +1^2)(d(1)^2+\cdots +d(n)^2)$

$\,\geq (d(1)+\cdots +d(n))^2$

以上から，$n\cdot n|E|\geq 4|E|^2$

となり示された。