题目

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

错因

A

握手定理用对了，但计数算错。可能是把"剩余度数和"算成 6 而不是 8（例如把 算成 10），最后凑出 3 + 4 + 3 = 10。基本套路对，单纯是算术失误。

C

剩余度数和 8 算对了，但为了"求最少"反而让其他顶点的度取小值——若让每个剩余顶点度为 1，需要 8 个顶点，总数 3 + 4 + 8 - 2 = 13。问题在于"求最少顶点数"的优化方向被搞反：要让顶点数少，每个剩余顶点的度数要大，单顶点贡献越大，需要的顶点就越少。

D

按"度均小于 3"取度为 1，剩余 8 度需要 8 个顶点，总数 3 + 4 + 8 = 15。和 C 一样把优化方向搞反，并且没意识到"度可取 0 / 1 / 2"里能取的最大值是 2。

总解析

核心工具：握手定理

Step 1：算总度数

边数 ，所以总度数 。

Step 2：扣掉已知顶点贡献的度数

• 度 4 的顶点 3 个，贡献
• 度 3 的顶点 4 个，贡献
• 已知贡献小计

剩余度数 ，需由"其他顶点"凑出。

Step 3：把"求最少顶点"翻译成"度数尽量集中"

题目要求顶点数最少，意味着分摊剩余 8 度的顶点要尽可能少。每个"其他顶点"的度数 ，所以单顶点最多贡献 2。

为最小化顶点数，让每个其他顶点都取最大值 2：

Step 4：累加

最终答案是 B（11）。

方向口诀："最少顶点 ↔ 单点度数取最大；最多顶点 ↔ 单点度数取最小"。这种"求最少/最多"题先盯住总度数（握手定理给出的硬约束），再判断每个顶点的"额度"上下界。