图兰定理

维基百科,自由的百科全书
跳转至: 导航搜索

Turán定理是一個與數學图论相关的理論。

设G为Kn的子图,而G不含完全图Kr+1。则G最多有\frac{r-1}{r}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{r} \right) \cdot\frac{n^2}{2}条边。这个定理叫做图兰定理Turán's theorem),由匈牙利数学家 Paul Turán 在1941年发现。