NOIP 普及组初赛 · NOIP 2016 普及组初赛试题 第 15 题

设简单无向图 $G$ 有 $16$ 条边且每个顶点的度数都是 $2$，则图 $G$ 有( )个顶点。

这题就是考握手定理：总度数=2×边数。拿到题先设顶点数为n，把“每个点度数都是2”翻译成等式n×2=2×16，直接解出n=16，别绕弯子。

很多学生看到“简单无向图”“每个点度数都是2”就下意识想画个环，然后纠结“16个点成环是不是简单图”“会不会有重边”，其实这是命题人设的陷阱。握手定理只管度数总和，跟图是否连通、是不是环没关系。就算图不连通，只要每个点度数都是2，总度数依然是2n，答案还是16。另一种常见错误是把公式记成“总度数=边数”，那样会算出n=8，直接掉进C选项的坑里。

这题考什么

这是一道图论基础计算题，核心考点就是握手定理（也叫度数握手定理）。命题人喜欢用“简单无向图”“每个点度数都是2”这种描述来掩盖本质，让学生以为要画图、要判断连通性，其实只要抓住度数总和与边数的关系就能秒杀。

概念：什么是握手定理

握手定理说：一个图中所有顶点的度数之和，等于边数的两倍。用公式写就是

\[\sum_{v\in V}\deg(v) = 2m\]

为什么是两倍？因为每条边都连着两个顶点，每个顶点从这条边那里各“拿”到1度，所以一条边对总度数的贡献是2。不管图长什么样，这个等式永远成立。