証明：
G が完全多部グラフであることを示す。完全多部グラフでないと仮定する。

各頂点を一つの部集合に割り当てれば、n 頂点のグラフは n 部集合に分けられる。隣接していない部集合を合体しても部集合のままであるから、隣接していない部集合がなくなるまで合体を繰り返す。完全多部グラフでないから、図のように、\(xy_1, xy_2 \notin E(G), y_1y_2 \in E(G)\) となる頂点 \(x,y_1,y_2\) が取れる。

(i) 次数 \( d(x) < d(y_1) \) のとき
頂点 \(x\) を消去して頂点 \(y_1\) を複製する。

(ii) 次数 \( d(x) < d(y_2) \) のとき
頂点 \(x\) を消去して頂点 \(y_2\) を複製する。

(iii) 次数 \( d(x) \geq d(y_1) \) かつ \( d(x) \geq d(y_2) \) のとき
頂点 \(y_1,y_2\) を消去して頂点 \(x\) を 2 回複製する。

いずれの場合も頂点数を不変のまま、\(K^r\) を含まないより辺数の多いグラフを構成できたので矛盾。従って G は完全多部グラフである。完全多部グラフのうち、辺数が最も多くなるのは Turán グラフのときであったから証明完了。

証明：
頂点数に関する帰納法で \(G\) が Turán グラフであることを示す。頂点数 \(n (< r)\) のとき \(G=K^n\) だから Turán の定理は成立。頂点数 \(n(\geq r)\) 未満のとき Turán の定理が成立することを仮定する。

辺数の最大性より、\(G\) に 1 辺 \(e\) を追加した \(G+e\) は \(K^r\) を部分グラフに含む。よって \(G\) は \(K^{r-1}\) を部分グラフに持つ。部分グラフ \(K^{r-1}\) を 1 つ固定して \(K\) と置く。\(K\) の頂点を削除したグラフ \(G-K\) は \(K^{r}\) を部分グラフに持たないから、辺数は \(t_{r-1}(n-(r-1))\) で抑えられる。\(H\) の各頂点 \(v\) は \(K\) の高々 \(r-2\) 個の頂点としか隣接しない。さもなくば \(K * v \cong K^r\) が \(G\) の部分グラフとなり矛盾。以上から、次の不等式で \(G\) の辺数 \(||G||\) が抑えられる：
$$||G|| \leq t_{r-1}\left(n-(r-1)\right)+(n-(r-1))(r-2)+{r-1\choose 2}.$$下図から不等式の右辺は \(t_{r-1}(n)\) と等しい。\(||G||\) の辺数の最大性から不等号は等号で常に成立。よって \(G-K\) は Turán グラフ \(T^{r-1}(n-(r-1))\) である。\(K\) の各頂点 \(v\) を \(G-K=T^{r-1}(n-(r-1))\) の非隣接な頂点の部集合に追加すれば、\(G\) は Turán グラフ \(T^{r-1}(n)\) となる。

証明：
Turán グラフは \(K^r\) を含まないことについて辺極大である。従って、\(K^r\) を含まない辺数 \(t_{r-1}(n)\) のグラフが Turán グラフのみであることを示せばよい。なぜなら、辺数 \(t_{r-1}(n)+1\) 以上の \(K^r\) を含まないグラフが存在するならば、辺極大であるはずの Turán グラフを部分グラフに持ち矛盾するからである。

頂点数についての帰納法で示す。1頂点のときは成立。
\(|G|\) 頂点未満のとき成立を仮定する。
次数最小の頂点 \(v\) について \(G-v\) の辺数は \(t_{r}(n-1)\) 以上。\(G-v\) は \(K^r\) を含まないから帰納法の仮定より \(G-v=T^{r}(n-1)\) である。\(v\) が \(T^{r}(n-1)\) の全ての部集合の頂点と隣接すると \(K^r\) が生じてしまうから、\(G=T^{r}(n)\) となる。\(|G|\) 頂点のときも成立したので証明完了。

証明：
各頂点 \(i\) に \(\sum w_i = 1\) を満たすように非負の重み \(w_i\) を割り振る。\(S:=\sum_{(i,j)\in E(G)} w_iw_j\) を最大化してみよう。

非隣接な2頂点 \(u,v\) の隣接頂点の重みの総和が \(x,y\ (x \geq y)\) だとする。微小量 \(\varepsilon > 0\) に対して、$$x(w_u+\varepsilon)+y(w_v-\varepsilon) \geq xw_u+yw_v$$だから、\(S\) を減少させずに特定のクリークに重みを集めることができる。

頂点 \(1,2,\ldots,m\) からなるクリーク \(K^m\) に重みを集めると \(2S\) は次のようになる：\begin{align}
2\sum_{(i,j)\in E(K^m)} z_iz_j
=&\left(\sum_{i=1}^m z_i\right)^2-\sum_{i=1}^m z_i^2\\
=&1-\sum_{i=1}^m z_i^2\\
\leq&1-\frac{1}{m}\sum_{i=1}^m z_i\\
=&1-\frac{1}{m}
\end{align}2行目から3行目にかけてコーシー・シュワルツの不等式を用いた。等号は \(z_i=1/m\) のとき成立。 \(m\) が大きいほどその値は大きくなる。\(G\) は \(K^r\) を部分グラフに持たないことについて辺極大だから、\(K^{r-1}\) を部分グラフに持つ。全ての重みが \(z_{i}=1/n\) のとき \(S=\frac{||G||}{n^2} \frac{1}{2}\leq (1-\frac{1}{r-1})\) であるから $$||G||\leq \frac{n^2}{2}\frac{r-2}{r-1}$$を得る。

証明：
クリークをなす頂点集合 \(U\) のサイズを求めたい。
\(\{1,2,\ldots,n\}\) のランダムな置換 \(\{\pi(1),\pi(2),\ldots,\pi(n)\}\) の先頭から順に頂点 \(v=\pi(i)\) を選ぶ。最初 \(U\) は空集合である。頂点 \(v\) を \(U\) に加えてもクリークならば、\(U\) に \(v\) を加える。\(v\) が \(U\) に加えられる確率は \(v\) が、 \(v\) の隣接頂点以外の頂点 \(n-d(v)-1\) 個より先に選ばれる確率 \(\frac{1}{n-d(v)}\) と等しい。よって \(|U|\) の期待値は \(\sum_{v \in V(G)} \frac{1}{n-d(v)}\) であるから \(G\) は必ずサイズ \(\lceil\sum_{v\in V(G)} \frac{1}{n-d(v)}\rceil\) 以上のクリークを部分グラフに持つ。

\(|G|\) が \(K^r\) を部分グラフに持たないという条件から次を得る：\begin{align}
r-1 \geq &\sum_{v \in V(G)} \frac{1}{n-d(v)}\\
\geq &\frac{n}{n-\sum_{v \in V(G)} \frac{d(v)}{n}}\\
=&\frac{n}{n-\frac{2||G||}{n}}
\end{align}2行目から3行目にかけてイェンセンの不等式を用いた。\(G\) について解いて \(||G||\leq \frac{n^2}{2}\frac{r-2}{r-1}\) を得る。