艾狄胥-斯通定理

中，艾狄胥－斯通定理（）是禁止某子圖出現後，圖邊數的漸近上界，推廣了图兰定理（即僅允許為完全圖的情況）。定理由埃尔德什·帕尔與於1946年證明，因而得名。稱其為「極值圖論的」。

圖蘭圖的極值函數
先定義極值函數（）如下：是眾多個頂點的圖之中，不包含子圖（同構於）的圖的邊數最大值。圖蘭定理斷言，當取為完全圖時，有，即個頂點的部的邊數，且僅得該圖蘭圖取到最大值。艾狄胥－斯通定理推廣到禁止子圖的情況，即禁止各分部恰有個頂點的完全部圖（亦可記為）：

任意非二部圖的極值函數
若為任意圖，色數為，則對於足夠大的，必為的子圖（比如取大於的某個染色中，用得最多的顏色所用的次數），但並非圖蘭圖的子圖，因為該圖蘭圖的任意子圖皆可染色。 

由此可見，的極值函數至少為的邊數，但至多為的極值函數。所以，仍有

然而，對於二部圖，定理給出的上界並非最優，因為已知當為二部圖時，，不過對於一般二部圖的極值函數，仍然所知甚少，見。

定量結果

定理亦有若干個定量版本已獲證，較確切刻劃與餘項的關係。先對，定義為最大的，使得子圖能於任意具個頂點及

條邊的圖中找到。

艾狄胥、斯通證明對充份大的，有

其中是對數函數的次疊代。的正確增長階數，由博洛巴什與艾狄胥找出：固定，則存在常數與使得

赫瓦塔爾與塞邁雷迪隨後確定如何隨和變化（但可以差常數倍）：對充份大的，有

參考文獻

图论
数学定理