简单图G有n个结点,e条边,设e>(n-1)(n-2)/2,证明G是连通的

发布网友发布时间：2024-05-14 17:47

共2个回答

热心网友时间：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和其它结点相连，所以此时这个图是连通的。结论成立。

热心网友时间：1天前

假设图是不连通的，则可以把n个结点分成m,(n-m)两部分(0<m<n)，两部分不连通。所以此简单图最多只能有 C(m,2)+C(n-m,2)=m(m-1)/2 + (n-m)(n-m-1)/2=[n^2-2mn+2m^2-n]/2 条边。要令这>(n-1)/(n-2)/2，则需要
n-m(n-m)>1
但n-m(n-m)=1只有在m=1或m=n-1时才成立，而在1<m<n-1时则n-m(n-m)<1，所以m不存在，即图是连通的。