🏷️ 知识点：顶点度数

已知无向图 (G) 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其余顶点的度均小于 3。图 (G) 所含的顶点个数至少是（ ）。

A. 10 B. 11 C. 13 D. 15

[tag_link]

正确答案：B

结论

图 (G) 至少含有 11 个顶点，选项 B 正确。

推导

握手定理给出所有顶点度数之和 (2|E|=2\times16=32)。已知度为 4 和度为 3 的顶点贡献

[ 3\times4+4\times3=24。 ]

剩余顶点的度小于 3，且为了让顶点数尽可能少，应让它们尽量取最大的允许度数 2。设这样的顶点有 (x) 个，则 (24+2x=32)，解得 (x=4)。所以顶点总数至少为 (3+4+4=11)。

易错点

“度小于 3”意味着最大只能取 2，不能把余下度数 8 用 3 个顶点平均分摊；那会使每个顶点的度达到 (8/3)，且有顶点度为 3，违反条件。先用握手定理算余量，再用最大允许度数求最少顶点数。

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

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 的顶点。