托兰定理

托兰定理：平面上N个点,至少连【N^2/4】+1条线段必定存在三角形

如果一个n阶简单图，它不包括Kp，则其边数最大值为 （p-2)(n^2-r^2)/(2*(p-1))+r/2

其中r是n mod (p-1)

托兰定理的补形：

平面上N个点，任何三点存在一条直线，至少连NC2-[N^2/4]条线

托兰定理的证明：

设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]