jacky
问题补充说明：数·学·归·纳·法·
设连通图G有（n+1）个顶点，来自若每个顶点连出至少两条边，那么此时至少有n+1条边(任意图上率裂周内尼专充长所有顶点度数和等于边数的两倍),结论已经成立。否则，那么至少有一个顶点只连出一条边。
不妨设为A，由于去掉这条边AB后不影响其戚薯他点的连通性，那么剩下的n个点之间有归纳假设至少有（n-1)条边，所以G至少有n条边。
任意一条边都代表u连360问答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。
参考资料来源：百度百科--连通无向图
