已知无向图 (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，违反条件。先用握手定理算余量，再用最大允许度数求最少顶点数。