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

问题描述:

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

有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