GESP 七级 · GESP 202603 C++ 七级 第 4 题

对于一棵包含 $n$ 个顶点（$n \ge 2$）的树，其所有顶点的度数之和必定等于（ ）。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】图论基础｜握手定理｜树的边数性质

【考纲定位】GESP七级图论模块明确要求掌握树的定义与性质。命题人卡住的是考生对"树"的本质理解——不是遍历、不是递归，而是"边数恒等于顶点数减一"。这道题就是检验你是否真正理解树的拓扑结构。

【解题思维】看到题先想"度数之和与边数的关系"——握手定理：所有顶点的度数之和等于边数的两倍。接着想"树的边数是多少"——定义决定：n个顶点的树必有n-1条边。两步推导：度数之和=2×边数=2(n-1)=2n-2。通法提炼：遇到求度数之和，先找边数；遇到树，先找边数恒等于顶点数减一。

【陷阱拆解】A是边数，C是顶点数乘2，D是完全图边数。命题人利用初学者易混淆度数之和与边数、顶点数的弱点，故意放这些看似合理的数字。最阴险的是C：很多人背过"握手定理"但记错系数，以为度数之和等于边数，或者误以为每个顶点贡献1度，结果算成2n。只背结论不推导，必选错。

【反命题思维】若把"树"换成"任意图且边数为m"，答案变成2m；若把"度数之和"换成"平均度数"，则是2(n-1)/n。这类题本质是考"度数定理与边数关系"的迁移能力。