证明：采用反证法。
假设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 是连通图。
