握手定理
概述
握手定理（Handshaking Theorem / Handshaking Lemma）：在无向图 中，所有顶点的度数之和恰好等于边数的两倍，即 。
定理陈述
形式化陈述
定理（握手定理）： 设 为无向图（允许有重边和环），则
推论：在任何无向图中，度数为奇数的顶点个数一定是偶数。
有向图版本：在有向图 中， 即所有顶点的入度之和等于所有顶点的出度之和，且都等于边数。
证明概要
证明思路
无向图版本
核心思想：每条边恰好对度数之和贡献 。
详细证明：
设 为无向图。对每条边 ：
- 边 恰好连接两个端点 和 （若 是连接 到自身的环，则 为 的度数贡献 ）。
- 因此，每条边 对 的贡献恰好为 。
将所有边的贡献相加：
证毕。
奇度数顶点个数为偶数的推论
设 为度数为奇数的顶点集合， 为度数为偶数的顶点集合。则：
因为 是偶数，且 是偶数（偶数之和仍为偶数），所以 也必须是偶数。
但 中每个顶点的度数都是奇数，奇数个奇数之和为奇数，只有偶数个奇数之和才为偶数。因此 必须是偶数。
有向图版本
对有向图 ，每条有向边 恰好：
- 为起点 的出度贡献
- 为终点 的入度贡献
因此：
证毕。
关键推论
- 推论1（奇度数顶点为偶数个）：如上所述，这是握手定理最常用的推论。可用于快速判断某个度数序列是否可能对应一个图。
- 推论2（度数序列可行性）：一个非负整数序列 能成为某个图的度数序列的必要条件是 为偶数。
- 推论3（正则图的边数）：-正则图（每个顶点度数均为 ）若有 个顶点，则边数为 ，因此 必须为偶数。
应用场景
- 图的度数序列验证：在判断一组度数是否能构成合法图时，握手定理提供必要条件。例如序列 的和为 （偶数），而 的和为 （奇数），后者不可能。
- 连通图 的边数下界： 个顶点的连通图至少有 条边（树），因为 。
- 社交网络分析：握手定理的”握手”隐喻——在一次聚会中，与他人握手次数的总和是握手总次数的两倍（每次握手涉及两个人）。
- 欧拉路径判定：图论 中判断欧拉路径/回路的存在性时，需要分析奇度数顶点的个数（ 个或 个），握手定理保证了这个讨论是有意义的。
数值示例
考虑无向图 ：顶点集 ，边集 。
度数：，，，。
验证：。
奇度数顶点：（度数 ）和 （度数 ），共 个（偶数）。