托兰定理
托兰定理:平面上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)
y≤-k^2+Nk=-(k-N/2)^2+[N^2/4]
当k=N/2时,y是整数,所以y的最大值为N^2/4
所以y≤[N^2/4]