託蘭定理

令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中幾乎一半的邊才能獲得無三角圖。

任何至少具有

條邊的哈密頓圖必須是完整的二分圖K(n/2),(n/2)或必須是全圈形的：不僅包含三角形，而且還必須包含所有其他可能長度到頂點數為止的迴路（Bondy 1971）。

Mantel定理的另一項加強説明，每個n頂點圖的邊最多可以被

點團覆蓋，它們可以是邊或三角形。 作為推論，相交數最多為

（Erdős，Goodman＆Pósa1966）。

設A為n個點中，向外連線最多的點，設它向外連k條線，則與A相連的點之間不允許連線

而剩餘(n-1-k)中的任意一點不可能向外連線數大於k，設這些點連線總數為y，則有

當

時，y是整數，所以y的最大值為

所以

。