在图论中，图兰定理是 K_(r+1)-free 图中边数的结果。

通过将一组顶点集划分为大小相等或几乎相等的r个部分，并在两个顶点属于两个不同子集的情况下，通过边连接两个顶点，可以形成不包含任何（r+1）个点团的n点图部分。我们称产生的图为托兰图 T(n,r)。图兰定理指出，托兰图在所有K_(r+1)-free的n点图中具有最多的边数。

托兰图是由匈牙利数学家帕尔托兰（PálTurán）于1941年首次描述和研究的，尽管曼特尔（Mantel）早在1907年就指出了该定理的一个特例。

基本定理

令G为具有n个顶点的任何图，使得G为K_(r+1)-free。

等效表达如下：

在没有(r+1)点团的n个顶点的简单图中，T(n,r)的边数最大。

参考资料