无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有（ ）个顶点。

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

图的概念

[tag_link]

正确答案：D

设图 G 的总顶点数为 n。 根据题意，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余顶点均为度为 2，故度为 2 的顶点数为 n - 5 - 4 = n - 9。 在无向图中，所有顶点的度之和等于边数的两倍。 已知边数为 23，因此总度之和为 2 × 23 = 46。 计算度之和：5 个度为 4 的顶点贡献 5×4=20，4 个度为 3 的顶点贡献 4×3=12，(n-9) 个度为 2 的顶点贡献 2(n-9)。 故有方程：20 + 12 + 2(n-9) = 46。 简化得 32 + 2n - 18 = 46，即 2n + 14 = 46，解得 2n = 32，n = 16。 因此，图 G 的顶点数为 16。 验证可行性：度序列由 5 个 4、4 个 3 和 7 个 2 组成，总度之和为 46，与边数一致，且满足图存在的基本条件（如握手引理）。 故最多有 16 个顶点，对应选项 D。