基本介紹
- 中文名：圖蘭定理
- 外文名：Turán's theorem
- 領域：圖論
定理,特殊情形,定理表述,Mantel定理的補形,Mantel定理的證明,
定理
托蘭定理，即圖蘭定理，詳見詞條圖蘭定理
定理的簡單表述如下：
如果一個n階簡單圖，它不包括Kp，則其邊數最大值為 （p-2)(n^2-r^2)/(2*(p-1))+r/2
其中r是n mod (p-1)
特殊情形
下面對於圖蘭定理r=2的著名情形給出證明。該情形也稱作Mantel's theorem
定理表述
平面上N個點,至少連[N^2/4]條線段必定存在三角形([x]表示不超過x的最大整數，即高斯函式)。
Mantel定理的補形
平面上N個點，任何三點存在一條直線，至少連NC2-[N^2/4]條線
Mantel定理的證明
設A為N個點中，向外連線最多的點，設它向外連k條線，則與A相連的點之間不允許連線
而剩餘N-1-k中的任意一點不可能向外連線數大於k，設這些點連線總數為y，則有
y≤k（N-1-k）+k
y≤-k^2+Nk=-(k-N/2)^2+[N^2/4]
當k=N/2時，y是整數，所以y的最大值為N^2/4
所以y≤[N^2/4]
