基本介紹
定理描述,證明,特殊情形,
定理描述
令G為具有n個頂點的任何圖，使得G為K_(r+1)-free。 那么G中的邊數最多為
等效表達如下：
在沒有(r+1)點團的n個頂點的簡單圖中，T(n,r)的邊數最大。
證明
令G為不具有(r+1)點團且具有最大邊數的n頂點的簡單圖。
概述：我們在證明之前進行簡要概述，以下的證明包括兩個關於G的聲明。
第一個聲明是G必須是完全r部圖（儘管下面會更詳細地說明）。換句話說，我們可以將頂點集劃分為r個子集S_1, S_2, … , S_r, 這樣，如果兩個頂點在不同的集合S_i 和 S_j 中，則它們之間有一條邊，但是如果它們是在同一組中，那么它們之間就沒有任何邊。
第二個聲明是這些集合S_i 的大小彼此相差最多1。例如，如果我們要在23個頂點上繪製圖，而且有最多的邊但不包含三角形，則可以對這些頂點進行劃分分為集合 S_1 和 S_2，其中 | S_1 | = 12， | S_2 | = 11。我們將兩組之間的所有邊相加，因此圖形將具有11 * 12 = 132條邊。這與定理匹配，該定理說G最多具有
條邊。
下面證明兩個聲明。
聲明1：圖G不包含任何三個頂點u,v,w，使得G包含邊uv，但不包含邊uw和vw。 （此聲明等同於關係x~y，如果x與y不相關，則為等價關係。〜總是自反且對稱的，但僅在特殊情況下，它是可傳遞的。~當我們具有u,v,w與u~w和w~v而沒有u~v）。
假設聲明是錯誤的。構造一個不包含(r+1)點團但具有比G多的邊的新n頂點簡單圖G'，如下所示：
情況1：
或者 
假設，刪除頂點w並創建頂點u的複製（所有鄰居都與u相同）；稱它為u'。新圖中的任何點團最多在{u,u'}中包含一個頂點。因此，此新圖不包含任何(r+1)點團。但是，它包含更多的邊：
情況2：
且
刪除頂點u和v並創建頂點w的兩個新複製。同樣，新圖不包含任何(r +1)點團。但是，它包含更多的邊：
這證明了聲明1。
這種說法證明，可以根據非鄰居將G的頂點劃分為等價類。也就是說，如果兩個頂點不相鄰，則它們在同一個等價類中。這意味著G是一個完全多部圖（其中部分是等價類）。
聲明2：如果部分的大小相差最多1個，則完全k部圖中的邊數將最大化。
如果G是具有A和B以及
的完全k分圖，則可以通過將頂點從A移動到B來增加G中的邊數。通過將頂點從A移動到B，圖將失去 |B| 邊數，但獲得 |A|-1 條邊。因此，它至少獲得了
條邊。這證明了聲明2。
該證明表明Turan圖具有最大數量的邊。此外，證明表明只有托蘭圖是具有最大邊數的圖。
特殊情形
下面對於托蘭定理 r=2 的著名情形給出證明。該情形也稱作Mantel's theorem。
定理表述
在不存在三邊迴路的n頂點圖中，邊數最大為
。
換句話說，必須刪除K_n中幾乎一半的邊才能獲得無三角圖。
Mantel定理的加強
任何至少具有條邊的哈密頓圖必須是完整的二分圖K(n/2),(n/2)或必須是全圈形的：不僅包含三角形，而且還必須包含所有其他可能長度到頂點數為止的迴路（Bondy 1971）。
Mantel定理的另一項加強說明，每個n頂點圖的邊最多可以被點團覆蓋，它們可以是邊或三角形。 作為推論，相交數最多為（Erdős，Goodman＆Pósa1966）。
Mantel定理的證明
設A為n個點中，向外連線最多的點，設它向外連k條線，則與A相連的點之間不允許連線
而剩餘(n-1-k)中的任意一點不可能向外連線數大於k，設這些點連線總數為y，則有
當
時，y是整數，所以y的最大值為
所以
。
