🏷️ 知识点：度序列

一个无向图有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余顶点的度均为 2，则该图有（ ）个顶点。

A. 11 B. 12 C. 15 D. 16

[tag_link]

正确答案：D

结论

该图有 16 个顶点。

推导

由握手定理，所有顶点度数之和为 2×23=46。度为 4 和 3 的顶点贡献 5×4+4×3=32，剩余顶点贡献 46−32=14。其余顶点度为 2，所以有 14÷2=7 个；总顶点数为 5+4+7=16。

易错点

边数不是度数和；无向图每条边连接两个端点，必须先用 2|E| 求度数总和，再除以其余顶点的度。