Erdős–Stoneの定理

$e(G)\le\binom n2< \frac{n^2}2$ なので、そのような $G$ があるなら $\varepsilon< \frac1r$ である。以下 $\varepsilon< \frac1r$ とし、整数 $M\ge r+1$ を $M-1\ge2/\varepsilon$ となるようにとる。$n\ge M$ とし、$V(G)$ の $M$ 元部分集合 $S$ 全体（$\binom nM$ 個）を考える。
平均．各辺はその両端を含む $\binom{n-2}{M-2}$ 個の $S$ に含まれるので、誘導部分グラフ $G[S]$ の辺の本数の平均は
$$ e(G)\frac{\binom{n-2}{M-2}}{\binom nM}=e(G)\frac{M(M-1)}{n(n-1)}\ge\Bigl(1-\frac1r+\varepsilon\Bigr)\frac{n^2}{n(n-1)}\binom M2\ge\Bigl(1-\frac1r+\varepsilon\Bigr)\binom M2 $$
である。
よい部分集合．$e(G[S])>(1-\frac1r)\frac{M^2}2$ となる $S$ を「よい」と呼び、その割合を $a$ とする。$M-1\ge2/\varepsilon$ から $\frac\varepsilon2\binom M2\ge(1-\frac1r)\frac M2$ なので、よくない $S$ は $e(G[S])\le(1-\frac1r)\frac{M^2}2\le(1-\frac1r+\frac\varepsilon2)\binom M2$ をみたす。よい $S$ でも $e(G[S])\le\binom M2$ なので、平均と比べて
$$ 1-\frac1r+\varepsilon\le a+(1-a)\Bigl(1-\frac1r+\frac\varepsilon2\Bigr) $$
であり、整理すると $\frac\varepsilon2\le a\bigl(\frac1r-\frac\varepsilon2\bigr)\le a$ である。
数える．よい $S$ は、Turánの定理 の系「辺の密度による形」により $(r+1)$-クリークを含む。1 つの $(r+1)$-クリークを含む $S$ は $\binom{n-r-1}{M-r-1}$ 個なので、$(r+1)$-クリークの個数を $Q$ とすると $Q\binom{n-r-1}{M-r-1}\ge a\binom nM$ である。$\binom nM\binom M{r+1}=\binom n{r+1}\binom{n-r-1}{M-r-1}$（$M$ 元集合とその中の $r+1$ 元集合の組を 2 通りに数える）と、$\binom n{r+1}\ge\bigl(\frac n{r+1}\bigr)^{r+1}$ により
$$ Q\ge\frac\varepsilon2\cdot\frac{\binom n{r+1}}{\binom M{r+1}}\ge\frac{\varepsilon}{2\binom M{r+1}(r+1)^{r+1}}\,n^{r+1} $$
である。$\delta:=\varepsilon\big/\bigl(2\binom M{r+1}(r+1)^{r+1}\bigr)$、$n_1:=M$ とすればよい。$\square$

$k$ についての帰納法で、すべての $s,\delta$ について示す。
$k=1$．辺は 1 元集合 $\{v\}$ で、$\delta n$ 個以上ある。$n\ge s/\delta$ なら $s$ 個の頂点 $v$ で $\{v\}$ が辺のものがとれ、それらを $V_1$ とすればよい。
$k\ge2$．$k-1$ のときは成り立つとする。$(V,E)$ を $n$ 頂点で $\lvert E\rvert\ge\delta n^k$ の $k$-一様ハイパーグラフとする（$E\ne\emptyset$ なので $n\ge k$ である）。$V$ の $(k-1)$ 元部分集合 $T$ に対し、$T$ に属さない頂点 $v$ で $T\cup\{v\}\in E$ となるものの集合を $D(T)$ とし、$d(T):=\lvert D(T)\rvert$ とおく。各辺は $k$ 通りに $T\cup\{v\}$ と書けるので $\sum_Td(T)=k\lvert E\rvert$ であり、$T$ は $\binom n{k-1}\le n^{k-1}/(k-1)!$ 個なので、$d(T)$ の平均 $\mu$ は $\mu\ge k!\,\delta n$ をみたす。
$T$ と、$D(T)$ に含まれる $s$ 元集合 $S$ の組 $(T,S)$ の個数を $Y$ とすると、$Y=\sum_T\binom{d(T)}s=\sum_Tf_s(d(T))$ である。Jensenの不等式と $f_s$ の単調性により $Y\ge\binom n{k-1}f_s(\mu)\ge\binom n{k-1}f_s(k!\,\delta n)$ である。$x:=k!\,\delta n\ge2s$ なら $x-s+1\ge x/2$ なので $f_s(x)\ge(x-s+1)^s/s!\ge(x/2)^s/s!$ であり、$\binom n{k-1}\ge\bigl(\frac n{k-1}\bigr)^{k-1}$ とあわせて
$$ Y\ge\Bigl(\frac n{k-1}\Bigr)^{k-1}\Bigl(\frac{k!\,\delta}2\Bigr)^s\frac{n^s}{s!} $$
である。$s$ 元集合 $S$ は $\binom ns\le n^s/s!$ 個なので、ある $S$ について、$S\subset D(T)$ となる $T$ が $\delta'n^{k-1}$ 個以上ある。ここで $\delta':=(k!\,\delta/2)^s/(k-1)^{k-1}$ である。
その $S$ を固定する。$S\subset D(T)$ なら $T\cap S=\emptyset$ である（$D(T)$ は $T$ の外の頂点からなる）。そこで、頂点集合 $V\setminus S$ の上の $(k-1)$-一様ハイパーグラフで、$S\subset D(T)$ となる $T$ をすべて辺とするものを考えると、$n-s$ 頂点で $\delta'n^{k-1}\ge\delta'(n-s)^{k-1}$ 本以上の辺をもつ。$n-s$ が $k-1$ のときの $N$（$s,\delta'$ に対するもの）以上なら、帰納法の仮定により、$V\setminus S$ の互いに交わらない部分集合 $V_1,\dots,V_{k-1}$（大きさ $s$）で、各 $V_i$ から 1 個ずつ選んだ $T=\{v_1,\dots,v_{k-1}\}$ がすべて $S\subset D(T)$ をみたすものがある。$V_k:=S$ とおくと、$v_k\in S$ について $T\cup\{v_k\}\in E$ なので、$V_1,\dots,V_k$ が求める完全 $k$ 部部分である。
したがって $N$ を、$n\ge s/\delta$ の条件（$k=1$）、または $k!\,\delta n\ge2s$ と $n-s$ が $k-1$ のときの $N$ 以上であることの条件（$k\ge2$）がみたされる大きさにとればよい。$\square$

$r,s,\varepsilon$ に対し lem-es-supersaturation の $\delta,n_1$ をとり、$k:=r+1$、$s$、$\delta$ に対し lem-es-hypergraph の $N$ をとる。$n_0:=\max\{n_1,N\}$ とする。
$n\ge n_0$ とし、$G$ を $e(G)\ge(1-\frac1r+\varepsilon)\frac{n^2}2$ の $n$ 頂点のグラフとする。lem-es-supersaturation により、$G$ の $(r+1)$-クリークのハイパーグラフは $\delta n^{r+1}$ 本以上の辺をもつ。lem-es-hypergraph により、互いに交わらない頂点の集合 $V_1,\dots,V_{r+1}$（大きさ $s$）で、各 $V_i$ から 1 個ずつ選んだ $r+1$ 個の頂点がつねに $(r+1)$-クリークをなすものがある。
$i\ne j$、$u\in V_i$、$w\in V_j$ とする。ほかの $V_l$（$l\ne i,j$）から頂点を 1 個ずつ選んで $u,w$ に加えると $(r+1)$-クリークができるので、$u$ と $w$ は隣接する。よって $V_1,\dots,V_{r+1}$ は $G$ の中で $K_{r+1}(s)$ をなす。$\square$

下から．$T(n,r)$ は部ごとに色を変えれば $r$ 色で塗り分けられるので、$T(n,r)$ が $H$ を含めば $\chi(H)\le r$ となり（彩色数 の命題「部分グラフと連結成分」）、$\chi(H)=r+1$ に反する。よって $\operatorname{ex}(n,H)\ge t(n,r)$ である。$T(n,r)$ の部の大きさ $n_1,\dots,n_r$ は $n/r+1$ 以下なので $\sum_in_i^2\le(n/r+1)n$ であり、
$$ t(n,r)=\frac12\Bigl(n^2-\sum_in_i^2\Bigr)\ge\Bigl(1-\frac1r\Bigr)\frac{n^2}2-\frac n2 $$
である。
上から．$H$ の $(r+1)$ 色の彩色をとり、色ごとの頂点の集合を $C_1,\dots,C_{r+1}$ とする。$h:=v(H)$ とおくと $\lvert C_i\rvert\le h$ であり、$C_i$ を $K_{r+1}(h)$ の第 $i$ の部に単射で写すと、$H$ の辺は異なる色の頂点を結ぶので $K_{r+1}(h)$ の辺に写る。よって $H$ は $K_{r+1}(h)$ に含まれる。$\varepsilon>0$ に対し、thm-es-main を $s=h$ で使うと、$n$ が十分大きければ $(1-\frac1r+\varepsilon)\frac{n^2}2$ 本以上の辺をもつ $n$ 頂点のグラフは $K_{r+1}(h)$、したがって $H$ を含む。よって $\operatorname{ex}(n,H)<(1-\frac1r+\varepsilon)\frac{n^2}2$ である。
上下の評価から $\operatorname{ex}(n,H)\big/\frac{n^2}2\to1-\frac1r$ であり、$\binom n2\big/\frac{n^2}2\to1$ なので $\operatorname{ex}(n,H)/\binom n2$ も同じ極限をもつ。$\square$