🏷️ 知识点：连通图边数

下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有顶点的度数之和为偶数； II. 边数大于顶点个数减 1； III. 至少有一个顶点的度为 1。

A. 只有 I B. 只有 II C. I 和 II D. I 和 III

[tag_link]

正确答案：A

结论

只有叙述 I 正确，答案为 A。

推导

由握手定理，所有顶点度数之和等于 (2|E|)，必为偶数。连通图的边数只需满足 (|E|\ge n-1)，树可取等号，所以 II 的“大于”不成立。环是连通图且所有顶点度为 2，说明连通图不保证存在度为 1 的顶点，III 也不成立。

易错点

把连通图的下界 (n-1) 误记成严格大于，或把“树至少有两个叶子”错误推广到所有连通图；含环的连通图可以没有度为 1 的顶点。