n阶无向简单图G，边数满足|e|>(n-1)(n-2)/2，证明

证明：采用反证法。

假设G不是连通图，并且由两子图G1,G2构成，G1的节点与G2的节点无交集，G1与G2之间无通路。n1是G1中的节点数，n2是G2的节点数。

则有，n1>=1，n2>=1，n = n1+n2，|e1|<=n1(n1-1)/2，|e2|<=n2(n2-1)/2。|e|=|e1|+|e2|，|e|<=n1(n1-1)/2+n2(n2-1)/2。【注：n1(n1-1)/2，n2(n2-1)/2 分别为 G1, G2 完全图的边数，即两子图最大可能的边数】

【注：这里的证明思路就是，若两子图的完全图边数之和都不能满足题中条件，说明假设不正确】

根据题意，若边数满足|e|>(n-1)(n-2)/2，

则 n1(n1-1)/2+n2(n2-1)/2>(n-1)(n-2)/2，

得到 n1(n1-1)/2+n2(n2-1)/2 - (n-1)(n-2)/2 > 0

=>(n1^2-n1)/2 + (n2^2-n2)/2 - (n^2-3n+2)/2 > 0

=>{ n1^2-n1 + n2^2-n2 - [ (n1+n2)^2 - 3(n1+n2) + 2 ] } / 2 > 0

=>[ n1^2 + n2^2 - (n1+n2) - (n1^2 + 2n1n2 + n2^2) + 3(n1+n2) - 2 ] / 2 > 0

=>[ n1^2 + n2^2 - (n1+n2) - n1^2 - 2n1n2 - n2^2 + 3(n1+n2) - 2 ] / 2 > 0

=>[ - 2n1n2 + 2(n1+n2) - 2 ] / 2 > 0

=>- n1n2 + (n1+n2) - 1 > 0

=>n1n2 - (n1+n2) + 1 < 0

我们知道，n1>=1，n2>=1，因此 n1n2 - (n1+n2) + 1 >= 0

所以 n1n2 - (n1+n2) + 1 < 0 不成立，假设不正确，因此 G 是连通图。