设n阶无向简单图G=，其中边数满足：│E│>(n－1)(n－2)/2，证明G是连通图。
证明：假设G不是连通图，不妨设G有两个连通分支G1和G2，且│V1│=n1，│V2│=n2，易见n1+n2=n，由于n1≥1，n2≥1，所以n1*n2-( n1+n2)+1≥0 （*）而│E1│≤n1(n1-1)/2, │E2│≤n2(n2-1)/2，从而│E│=│E1│+│E2│≤n1(n1-1)/2+ n2(n2-1)/2由式（*）可得，n1(n1-1)/2+ n2(n2-1)/2≤[(n1+n2)2-3(n1+n2)+2]/2=(n-1)(n-2)/2，即│E│≤(n－1)(n－2)/2这与题设条件│E│>(n－1)(n－2)/2矛盾，故G 是连通图。
