Question

设无向连通图G有n个顶点，证明G至少有（n-1）条边。

数·学·归·纳·法·

Answer 1

设连通图G有（n+1）个顶点，若每个顶点连出至少两条边，那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立。否则，那么至少有一个顶点只连出一条边。

不妨设为A，由于去掉这条边AB后不影响其他点的连通性，那么剩下的n个点之间有归纳假设至少有（n-1)条边，所以G至少有n条边。

任意一条边都代表u连v以及v连u。无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。

扩展资料：

有向图 G=(V，E) 中，若对于V中任意两个不同的顶点 x和 y，都存在从x到 y以及从 y到 x的路径。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。

一个无向图 G=(V，E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。 

如果 G=(V，E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。

参考资料来源：百度百科--连通无向图

Answer 2

设连通图G有（n+1）个顶点，若每个顶点连出至少两条边，那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立。否则，那么至少有一个顶点只连出一条边。不妨设为A，由于去掉这条边AB后不影响其他点的连通性，那么剩下的n个点之间有归纳假设至少有（n-1)条边，所以G至少有n条边。