Turánの定理

組 $(n_1,\dots,n_r)$ に、ある $i,j$ で $n_i\ge n_j+2$ となるものがあるとする。$n_i$ を $1$ 減らし $n_j$ を $1$ 増やすと、和 $n$ は変わらず、$\sum_kn_k^2$ の変化は
$$ (n_i-1)^2+(n_j+1)^2-n_i^2-n_j^2=-2(n_i-n_j-1)\le-2 $$
である。辺の本数の式 $\frac12\bigl(n^2-\sum_kn_k^2\bigr)$ により、$\sum_{k< l}n_kn_l$ は $n_i-n_j-1\ge1$ だけ真に増える。したがって最大値をとる組では、どの 2 つの差も高々 $1$ である（非負整数の組は有限個なので最大値は存在する）。
逆に、どの 2 つの差も高々 $1$ である組は並べ方を除いて一意である。実際、そのような組の最小値を $m$ とすると各 $n_i$ は $m$ か $m+1$ で、$m+1$ に等しいものの個数を $s'$（$0\le s'< r$ としてよい。$s'=r$ なら全部が $m+1$ で、最小値が $m+1$ になり矛盾する）とすると $n=mr+s'$ となるので、割り算の一意性から $m=q$、$s'=s$ である。したがってこの組は $T(n,r)$ の部の大きさの組であり、$\sum_{i< j}n_in_j$ の最大値は $t(n,r)$、最大値をとるのはこの組だけである。後半は、完全 $r$ 部グラフが部の大きさの組で同型を除いて決まることから従う。$\square$

$n$ と $r$ を固定する。$K_{r+1}$ を含まない $n$ 頂点のグラフは有限個しかないので、その中で辺の本数が最大のもの $G$ をとる。以下、$d(x)$ を $G$ での頂点 $x$ の次数(グラフ)、$N(x)$ を $G$ で $x$ に隣接する頂点の集合とする。
段階 1（複製）。 隣接しない 2 頂点 $u,v$ について、$u$ を取り除き、$v$ の「複製」$v'$ を加えたグラフ $G'$ を考える。$v'$ は $N(v)$ のすべての頂点と隣接し、$v$ とは隣接しない。$u$ と $v$ は隣接しないので $u\notin N(v)$ であり、$G'$ でも $v'$ はちょうど $d(v)$ 本の辺をもつ。したがって
$$ e(G')=e(G)-d(u)+d(v) $$
である。$G'$ は $K_{r+1}$ を含まない。実際、$G'$ のクリークは隣接しない $v,v'$ の両方を含むことはなく、$v'$ を含むクリークは $v'$ を $v$ に置き換えると $G$ のクリークになる（$v'$ と $v$ は同じ頂点に隣接し、$u$ はもう使われていない）。$G$ の辺の本数の最大性から $e(G')\le e(G)$、すなわち 隣接しない $u,v$ について $d(u)\ge d(v)$ である。$u$ と $v$ の役割を入れ替えれば $d(v)\ge d(u)$ でもあるので、隣接しない 2 頂点の次数は等しい。
段階 2（隣接しないことの推移性）。 $u,v,w$ を相異なる頂点とし、$uv\notin E(G)$、$vw\notin E(G)$ とする。$uw\notin E(G)$ を示す。$uw\in E(G)$ と仮定する。段階 1 により $d(u)=d(v)=d(w)$ である。$u$ と $w$ を取り除き、$v$ の複製 $v',v''$ を 2 つ加えたグラフ $G''$ を作る（$v',v''$ はそれぞれ $N(v)$ の頂点すべてと隣接し、$v$ とも互いとも隣接しない）。$u,w\notin N(v)$ なので、$v',v''$ はそれぞれ $d(v)$ 本の辺をもつ。取り除いた辺は $u$ に接続する $d(u)$ 本と $w$ に接続する $d(w)$ 本だが、辺 $uw$ を 2 回数えているので
$$ e(G'')=e(G)-\bigl(d(u)+d(w)-1\bigr)+2d(v)=e(G)+1 $$
である。段階 1 と同じ理由で $G''$ のクリークは $v,v',v''$ のうち高々 1 つを含み、それを $v$ に置き換えると $G$ のクリークになるので、$G''$ は $K_{r+1}$ を含まない。これは $G$ の最大性に反する。したがって $uw\notin E(G)$ である。
段階 3（完全多部グラフであること）。 頂点の間の関係「$x=y$ または $x$ と $y$ が隣接しない」は反射的・対称的であり、段階 2 により推移的なので、同値関係である。その同値類を $V_1,\dots,V_p$ とすると、同じ同値類の 2 頂点は隣接せず、異なる同値類の 2 頂点は隣接する。したがって $G$ は部 $V_1,\dots,V_p$ をもつ完全 $p$ 部グラフである。各 $V_i$ から 1 頂点ずつ選ぶと互いに隣接する $p$ 頂点が得られるので、$G$ が $K_{r+1}$ を含まないことから $p\le r$ である。空の部を $r-p$ 個加えれば、$G$ は $n$ 頂点の完全 $r$ 部グラフとみなせる。
段階 4（結論）。 lem-turan-theorem-balanced により $e(G)\le t(n,r)$ である。$G$ は辺の本数が最大のものだったので、$K_{r+1}$ を含まない任意の $n$ 頂点のグラフ $H$ について $e(H)\le e(G)\le t(n,r)$ である。
等号の場合を示す。$H$ が $K_{r+1}$ を含まず $e(H)=t(n,r)$ を満たすとする。$T(n,r)$ も $K_{r+1}$ を含まないので、辺の本数の最大値は $t(n,r)$ であり、$H$ もその最大値をとる。段階 1〜3 は最大値をとるグラフなら何にでも使えるので、$H$ は完全 $r$ 部グラフであり、$e(H)=t(n,r)$ と lem-turan-theorem-balanced の等号条件から $H$ は $T(n,r)$ と同型である。$\square$

$n>r$ なので $T(n,r)$ の部の大きさ $n_1,\dots,n_r$ はどれも $q\ge1$ 以上である。各部から 1 頂点ずつ、計 $r$ 頂点を取り除くと、部の大きさは $n_i-1$ になり、差は高々 $1$ のままなので、残りは $T(n-r,r)$ と同型である。取り除いた辺は、取り除いた $r$ 頂点どうしを結ぶ $\binom r2$ 本と、取り除いた頂点と残った頂点を結ぶ辺である。部 $V_i$ から取り除いた頂点は、残った $n-r$ 頂点のうち $V_i$ に残る $n_i-1$ 頂点以外のすべてと隣接するので、後者の本数は
$$ \sum_{i=1}^r\bigl((n-r)-(n_i-1)\bigr)=r(n-r)-(n-r)=(r-1)(n-r) $$
である。$\square$

$r\ge1$ を固定し、$n$ に関する強い数学的帰納法で $e(G)\le t(n,r)$ を示す。$n\le r$ なら $T(n,r)=K_n$ なので $e(G)\le\binom n2=t(n,r)$ である。
$n>r$ とし、$n$ より少ない頂点数では主張が成り立つとする。$K_{r+1}$ を含まない $n$ 頂点のグラフ $G$ に、$K_{r+1}$ を含まないという条件を保ったまま辺を 1 本ずつ加えられるだけ加えたグラフを $G^+$ とする。$e(G)\le e(G^+)$ なので、$G^+$ について示せばよい。$G^+$ は $K_{r+1}$ を含まないので完全グラフではなく（$n>r$）、隣接しない 2 頂点 $x,y$ がある。辺 $xy$ を加えると $K_{r+1}$ ができるので、$G^+$ には $x$ と、$x,y$ の両方に隣接する $r-1$ 個の頂点とが互いに隣接する $r$ 頂点の集合 $S$ がある。すなわち $G^+$ は $K_r$ を含む。
$S$ の外の頂点 $z$ は、$S$ の $r$ 頂点すべてと隣接することはない（隣接すれば $S\cup\{z\}$ が $K_{r+1}$ になる）ので、$S$ と $z$ を結ぶ辺は高々 $r-1$ 本である。したがって $S$ と $S$ の外を結ぶ辺は高々 $(r-1)(n-r)$ 本、$S$ の中の辺は $\binom r2$ 本である。$S$ を取り除いた $n-r$ 頂点のグラフ $G^+-S$ も $K_{r+1}$ を含まないので、帰納法の仮定により $e(G^+-S)\le t(n-r,r)$ である。これらを合わせ、lem-turan-theorem-recursion を使うと
$$ e(G^+)\le t(n-r,r)+(r-1)(n-r)+\binom r2=t(n,r) $$
である。$\square$

$T(n,r)$ の部の大きさを $n_1,\dots,n_r$ とすると、Cauchy–Schwarzの不等式により $n^2=\bigl(\sum_in_i\bigr)^2\le r\sum_in_i^2$ であり、等号は $n_1=\cdots=n_r$ のとき、すなわち $r\mid n$ のときに限る（部の大きさの差が高々 $1$ なので、すべて等しいことは $s=0$ と同じである）。したがって
$$ t(n,r)=\frac12\Bigl(n^2-\sum_in_i^2\Bigr)\le\frac12\Bigl(n^2-\frac{n^2}r\Bigr)=\left(1-\frac1r\right)\frac{n^2}2 $$
である。後半は thm-turan-theorem-main から従う。$\square$

頂点の並べ方（$V(G)$ の元を一列に並べる方法）は $n!$ 通りある。並べ方 $\sigma$ に対し、隣接するどの頂点よりも前に並んでいる頂点の集合を $I_\sigma$ とする。$I_\sigma$ は独立集合である。実際、隣接する $u,v$ がともに $I_\sigma$ に属すれば、$u$ は $v$ より前にあり、$v$ は $u$ より前にあることになって矛盾する。
頂点 $v$ が $I_\sigma$ に属するのは、$v$ と $v$ に隣接する $d(v)$ 頂点の計 $d(v)+1$ 頂点の中で $v$ が最初に並ぶときである。この $d(v)+1$ 頂点の並ぶ順番は $n!$ 通りの並べ方の中で均等に現れるので、そのような $\sigma$ は $n!/(d(v)+1)$ 通りある。したがって
$$ \sum_\sigma|I_\sigma|=\sum_v\#\{\sigma\mid v\in I_\sigma\}=\sum_v\frac{n!}{d(v)+1} $$
であり、$|I_\sigma|$ の平均は $\sum_v\frac1{d(v)+1}$ である。平均以上の $|I_\sigma|$ をもつ $\sigma$ があるので、第 1 の不等式が従う。
第 2 の不等式は、Cauchy–Schwarz の不等式 $\bigl(\sum_va_v\bigr)\bigl(\sum_va_v^{-1}\bigr)\ge n^2$（$a_v:=d(v)+1>0$）と、握手補題 $\sum_vd(v)=2m$（次数(グラフ) の記事を参照）による $\sum_va_v=2m+n$ から従う。$\square$