Question

怎么证明:n个结点的连通图,至少有n-1条边??~

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