Question

证明n个顶点k条边的简单图G,若k>1/2(n-1)(n-2),则图G是连通的.

Answer 1

有G和G的补图,K+K（补）=n(n-1)/2
设G不连通,则G的补图是连通,K（补）>=n-1;
k+k(bu)>=k+n-1;
k+k(bu)=n(n-1)/2;
推出k