设n阶无向简单图G= ,其中边数满足:|E|> (n-1)(n-2)/2，证明G是连通图。

设n阶无向简单图G= ,其中边数满足:|E|> (n-1)(n-2)/2，证明G是连通图。

证明:假定C不是连通图,不妨设G有两个连通分支G1 和C2 ，且|V1| =nI，|V2| =n2
易见nl+n2=n
由于n1≥1,n2≥1
所以n1n2-(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)²-3(n1+n2)+2]/2=(n-1)(n-2)/2
即|E|≤(n-1)(n-2)/2
这与题设条件|E|> (n-1)(n-2)/2矛盾
故G是连通图