简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的问题如题所示,谢谢数学高手解答

Question

简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的
问题如题所示,谢谢数学高手解答

Answer 1

证明：在图G中,它的结点数为n,设v是G中任一结点,若把v去掉后,其它n-1结点,每个结点度数最多有n-1度,因此n-1个结点之间最多只有（n-1）(n-2)/2条边,而e＞(n-1)(n-2)/2,所以至少有一条边连接v和其它结点.
　下面用数学归纳法进一步证明：
（1）容易证明当n=1,2时,结论成立
（2）假设当n=k时,结论成立,即若e＞（k-1）(k-2)/2时结论成立
（3）当n=k+1时,若此时每个结点度数为k,则结论显然成立,否则必存在一个结点v度数至多只有k-1度,即这个结点最多只有k-1条边和它相连.因为此时总的边数e>k(k-1)/2,则其它k个结点之间的边数e'＞k(k-1)/2-(k-1)=(k-1)(k-2)/2.根据归纳假设,显然这k个结点之间是连通的,而根据上面我们知道,至少有一条边使v和其它结点相连,所以此时这个图是连通的.结论成立.