图兰定理(Turán theorem),理学-数学-图论-匹配,匈牙利数学家P.图兰(Pál Turán,1910-08-18~1976-09-26)在1941年首次提出的定理。此定理是极值图论这个重要图论分支的基础,它刻画了含有个顶点且不包含大小为的团的简单图所具有的最大边数。又译托兰定理。这个定理具体叙述为:设是有个顶点的简单图,若不包含完全图,则:。等号成立当且仅当,式中是具有个顶点的完全部图,它的每一部的顶点数尽可能地相等,这样的图称为图兰图。图兰还证明了具有个顶点、条边的简单图总包含由个顶点构成的完全子图。如果对任意的,都有,则称实数列弱于实数列。如果的不减度序列弱于的不减度序列,则称图弱度于图。爱尔特希在1970年给出了一个更强的结论:若简单图不包含,则度弱于某个完全部图。若具有和相同的度序列,则。用这个结论可以推导出图兰定理。由图兰定理可知,若一个图的顶点数为,边数为,则一定包含完全图。