艾狄胥－斯通定理

先定义极值函数（英语：extremal function）${\displaystyle \mathrm {ex} }$ 如下：${\displaystyle \mathrm {ex} (n;H)}$ 是众多${\displaystyle n}$ 个顶点的图之中，不包含子图（同构于）${\displaystyle H}$ 的图的边数最大值。图兰定理断言，当${\displaystyle H}$ 取为完全图${\displaystyle K_{r}}$ 时，有${\displaystyle \mathrm {ex} (n;K_{r})=t_{r-1}(n)}$ ，即${\displaystyle n}$ 个顶点的${\displaystyle r-1}$ 部图兰图（英语：Turán graph）的边数，且仅得该图兰图取到最大值。艾狄胥－斯通定理推广到禁止${\displaystyle K_r(t)}${\displaystyle K_{r}(t)}  子图的情况，即禁止各分部恰有${\displaystyle t}$ 个顶点的完全${\displaystyle r}$ 部图（亦可记为图兰图（英语：Turán graph）${\displaystyle T(rt,r)}$ ）：

${\displaystyle {\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$ 

若${\displaystyle H}$ 为任意图，色数为${\displaystyle r>2}$ ，则对于足够大的${\displaystyle t}$ ，${\displaystyle H}$ 必为${\displaystyle K_{r}(t)}$ 的子图（比如取${\displaystyle t}$ 大于${\displaystyle H}$ 的某个${\displaystyle r}$ 染色中，用得最多的颜色所用的次数），但${\displaystyle H}$ 并非图兰图${\displaystyle T(n,r-1)}$ 的子图，因为该图兰图的任意子图皆可${\displaystyle r-1}$ 染色。

由此可见，${\displaystyle H}$ 的极值函数至少为${\displaystyle T(n,r-1)}$ 的边数，但至多为${\displaystyle K_{r}(t)}$ 的极值函数。所以，仍有

${\displaystyle {\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$ 

然而，对于二部图${\displaystyle H}$ ，定理给出的上界并非最优，因为已知当${\displaystyle H}$ 为二部图时，${\displaystyle \mathrm {ex} (n;H)=o(n^{2})}$ ，不过对于一般二部图的极值函数，仍然所知甚少，见扎兰凯维奇问题（英语：Zarankiewicz problem）。

定理亦有若干个定量版本已获证，较确切刻划${\displaystyle n,r,t}${\displaystyle n,r,t}  与余项${\displaystyle o(1)}$ 的关系。先对${\displaystyle 0<\varepsilon <1/(2(r-1))}$ ，定义[3]${\displaystyle s_{r,\varepsilon }(n)}$ 为最大的${\displaystyle t}$ ，使得子图${\displaystyle K_{r}(t)}$ 能于任意具${\displaystyle n}$ 个顶点及

${\displaystyle \left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}}$ 

条边的图中找到。

艾狄胥、斯通证明对充份大的${\displaystyle n}$ ，有

${\displaystyle s_{r,\varepsilon }(n)\geq \left(\log ^{r-1}n\right)^{1/2},}$ 

其中${\displaystyle \log ^{r-1}}$ 是对数函数的${\displaystyle r-1}$ 次迭代。${\displaystyle s_{r,\varepsilon }(n)}$ 的正确增长阶数，由博洛巴什与艾狄胥找出：^[4]固定${\displaystyle r,\varepsilon }$ ，则存在常数${\displaystyle c_{1}(r,\varepsilon )}$ 与${\displaystyle c_{2}(r,\varepsilon )}$ 使得

${\displaystyle c_{1}(r,\varepsilon )\log n<s_{r,\varepsilon }(n)<c_{2}(r,\varepsilon ).}$ 

赫瓦塔尔与塞迈雷迪^[5]随后确定${\displaystyle s_{r,\varepsilon }(n)}$ 如何随${\displaystyle r}$ 和${\displaystyle \varepsilon }$ 变化（但可以差常数倍）：对充份大的${\displaystyle n}$ ，有

${\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n.}$