握手引理

在图论中，握手引理（英语：handshaking lemma）为在每个有限无向图中，顶点邻接奇数个边的数量有偶数个。也可以说，度数为奇数的顶点有偶数个。例如，在某派对上大家互相握手，则“跟奇数个人握手的人”有偶数个。^[1]此引理是由度求和公式（英语：degree sum formula）推导而得，内容为无向图中所有顶点的度数（邻接到该顶点的边数）总和为该图边数的两倍。上面的两个结果都由 李昂哈德‧欧拉 （1736）在他著名的柯尼斯堡七桥问题的论文上证明，也就是图论研究的起点。^[2]

此图中，有偶数个顶点（编号为2、4、5、6的四个顶点）的度数为奇数。所有六个顶点的度数总和为 2+3+2+3+3+1=14，是边数的两倍。

除了后来催生一笔画问题的柯尼斯堡七桥问题之外，度求和公式的其他应用还包括了某些组合结构的证明。例如，在斯苯纳引理（英语：Sperner's lemma）和爬山问题的证明中，该公式的几何特性经常出现。复杂度类 PPA 概括了在给定大型隐式定义图（英语：Implicit graph）中给定一个奇数顶点的情况下，找出第二个奇数顶点的难度。

定义与陈述

在无向图中，包含一系列的顶点与连接无序顶点对的边。在任何的图中，顶点 ${\displaystyle v}$ 的度数 ${\displaystyle \deg(v)}$ 定义为以 ${\displaystyle v}$ 为端点的边的数量。对于允许包含连接顶点本身，也就是包含环的图，为了符合握手引理，每个环应该对其端点的度数贡献两单位（即有环的顶点本身度数加二）。^[3]然后握手引理指出，在每个有限无向图中，度数 ${\displaystyle \deg(v)}$ 为奇数的顶点数必须为偶数。^[4]图中度数为奇数的顶点有时称为奇顶点（或奇节点）；^[5] 以此术语而言，握手引理可改述为“每个图都有偶数个奇顶点”的陈述。^[5][6]

度求和公式指出：$${\displaystyle \sum _{v\in V}\deg v=2|E|,}$$其中 ${\displaystyle V}$ 是图中节点（或顶点）的集合且 ${\displaystyle E}$ 是图中边的集合。也就是说，顶点度数的总和等于边数的两倍。^[7] 在有向图中，度求和公式的另一种形式指出，所有顶点的入度（英语：in-degree）之和与出度（英语：out-degree）之和皆等于边的数量。这里的入度是指“起点为某节点的边的数量”，出度是指“终点为某节点的边的数量”。^[8] 度求和公式的一个版本也适用于有限的集族，等价于多重图：元素度数的总和（其中度数等于包含它的集合的数量）总是等于集合的势总和。^[9]

这两个结果也适用于给定图的任何子图，特别是其连通元件。推论是对于任何奇数顶点，必存在一条路径将其连接到另一个奇顶点。^[10]

应用

欧拉路径与回路

柯尼斯堡七桥示意图

以每块陆地为顶点，每座桥为边的图

莱昂哈德·欧拉在研究柯尼斯堡七桥问题时首次证明了握手引理。这个问题是关于如何在柯尼斯堡（现为加里宁格勒）城中进行一次徒步旅行，跨过七座桥，且每座桥都只能走一次。以图论的术语来说，相当于在一个代表城市和桥梁的连通图中寻找一条欧拉路径（英语：Euler path）或欧拉回路（英语：Euler tour）：遍历图中每条边一次的路径，其区别为欧拉路径的起点和终点不同，而欧拉回路行径则会回到起点。

欧拉根据图中奇顶点的数量阐述了此问题的基本结果，握手引理则将奇数顶点的数量限制为偶数。如果奇顶点的数量为零，则存在欧拉回路；如果为两个，则存在欧拉路径。否则，问题就无法解决。在柯尼斯堡七桥问题中，代表该问题的图有四个奇数顶点，因此既不存在欧拉路径，也不存在欧拉回路。^[2]这表示在柯尼斯堡，不可能在不重复过桥的情况下走完所有七座桥。

在近似旅行推销员问题（缩写为 TSP）的克里斯托菲德斯算法中，度求和公式的几何意义扮演着至关重要的角色，使该算法得以将顶点成对连接，从而构建一个图，并在此图上形成一个欧拉回路作为近似 TSP 路径。^[11]

组合计数

某些组合结构的数量可以透过将它们与适当的“交换图（exchange graph）”中的奇顶点相关联来证明其为偶数。^[12]

举例，如 C. A. B. Smith（英语：Cedric Smith (statistician)） 所证，在任何立方图 ${\displaystyle G}$ 中，通过任何固定边 ${\displaystyle uv}$ 的汉米顿循环数量必为偶数；这些循环恰好经过每个顶点一次。汤玛森 (1978) harvtxt模板错误: 无指向目标: CITEREF汤玛森1978 (帮助) 则是利用基于握手引理的证明，将此结果推广到所有顶点都具有奇数度数的图。汤玛森定义一个交换图 ${\displaystyle H}$，其顶点与 ${\displaystyle G}$ 中始于 ${\displaystyle u}$ 并持续通过边 ${\displaystyle uv}$ 的汉米顿路径一一对应。若一条路径 ${\displaystyle p_{2}}$ 可透过在 ${\displaystyle p_{1}}$ 的末端添加一条新的边并从 ${\displaystyle p_{1}}$中间移除另一条边来获得，那么 ${\displaystyle p_{1}}$ 和 ${\displaystyle p_{2}}$ 这两条路径在 ${\displaystyle H}$ 中被定义为透过一条边连接。此操作是可逆的，形成一个对称关系，因此 ${\displaystyle H}$ 是一个无向图。若路径 ${\displaystyle p}$ 结束于顶点 ${\displaystyle w}$，则 ${\displaystyle H}$ 中对应于 ${\displaystyle p}$ 的顶点的度数等于 ${\displaystyle p}$ 可透过不连接回 ${\displaystyle u}$ 的边进行扩展的方法数；也就是若 ${\displaystyle p}$ 不构成通过 ${\displaystyle uv}$ 之汉米顿循环的一部分，则 ${\displaystyle H}$ 中此顶点的度数为 ${\displaystyle \deg(w)-1}$（偶数）；若 ${\displaystyle p}$ 通过 ${\displaystyle uv}$ 之汉米顿循环的一部分，则为 ${\displaystyle \deg(w)-2}$（奇数）。因为 ${\displaystyle H}$ 具有偶数个奇顶点，因此 ${\displaystyle G}$ 必须有偶数个通过 ${\displaystyle uv}$ 的汉米顿循环。^[13]

其他应用

握手引理（或度求和公式）在数学中也用于证明其他几项结果。其中包括：

经过斯苯纳染色的三角形分割图，其中阴影部分标示出具所有三种颜色的顶点之小三角形。

• 斯苯纳引理（英语：Sperner's lemma）指出，若一个大三角形被细分成边对边相接的小三角形，且顶点会被标上三种颜色，使得大三角形的每条边上只使用其中的两种颜色，那至少有一个小三角形的顶点会包含所有三种颜色；此引理应用于不动点定理、求根算法，与公平分配赛局。其中一个证明方法是构造一个交换图，其顶点是这些（大大小小）的三角形且其边连接的是共享某两种特定颜色的两个顶点的三角形对。这个交换图中，大三角形的度数必然是奇数，具所有三种颜色的小三角形的度数也为奇数，而其他小三角形的度数则为偶数。根据握手定理，具所有三种颜色的小三角形的数量必为奇数，因此至少存在一个这样的小三角形。^[14]

爬山问题

• 爬山问题指出，对于单位区间上的良态，且区间两端点函数数值相等的函数，可以协调从两个区间端点同时出发的点的运动（如动画所示），使它们在区间内的某点相遇，并且在整个运动过程中始终保持在函数值相等的位置。该问题的证明方法之一，需要一个近似原始函数的，具相同极值点的分段线性函数（英语：Piecewise linear function）。接着透过单位正方形中单一点的座标来参数化两个移动点的位置。最后，证明两个点的可移动位置形成一个嵌入在此单位正方形中的有限图，而该图中只有起始位置及其反向位置为奇顶点。根据握手定理，这两个位置属于图中的同一个连通元件，因此从一个位置到另一个位置的路径必然会经过所需的相遇点。^[15]
• 重构猜想是关于从移除单一顶点所形成的子图多重集来唯一确定图结构的问题。给定这些资讯，度求和公式可以用来恢复原始图中的边数以及每个顶点的度数，而从中可以判断给定图是否为正则图。如果是，则可以通过为所有度数过低的子图顶点添加新邻居，从任何一个删除顶点的子图中唯一地确定该正则图。因此，所有正则图都可以被重构。^[16]
• 六贯棋（Hex）是一种由两名玩家进行的游戏。玩家轮流在由六边形方格组成的平行四边形棋盘上放置自己颜色的棋子，直到其中一名玩家的棋子从棋盘的一边连接到另一边，形成一条连续的路径为止。这个游戏永远不会出现平局：当棋盘完全被棋子填满时，其中一名玩家必然已经形成了一条获胜路径。证明这一点的方法之一是从一个已经下满棋子的棋盘构造一个图。在这个图中，六边形的角点是顶点，而分隔两种玩家颜色的六边形边缘则是边。这个图在棋盘的四个角点有四个奇顶点，其他地方的顶点则都是偶数。因此，它必然包含一条连接两个角点的路径，这条路径的其中一侧必然属于其中一名玩家的获胜路径。^[17]

证明

欧拉证明度求和公式时使用了双重计数的技巧：他以两种不同的方式，计算了关联对 ${\displaystyle (v,e)}$ 的数量，其中 ${\displaystyle e}$ 是一条边，且顶点 ${\displaystyle v}$ 是它的其中一个端点。顶点 ${\displaystyle v}$ 属于 ${\displaystyle \deg(v)}$ 个关联对，其中 ${\displaystyle \deg(v)}$（${\displaystyle v}$ 的度数）是与它邻接的边的数量。因此，关联对的数量就是所有度数的总和。然而，图中的每条边都恰好属于两个关联对，每个端点一个；因此，关联对的数量是 ${\displaystyle 2|E|}$。由于这两个公式计算的是同一组物件，它们的值必然相等。同样的证明也可以解释为：透过两种方式对图的关联矩阵（英语：Incidence matrix）中的条目进行求和，按行求和得到度数的总和，按列求和得到边数的两倍。^[6]

对于图而言，握手引理是度求和公式的直接推论。^[9]在整数的和中，总和的奇偶性不受总和中偶数项的影响；当奇数项的数量为偶数时，总和为偶数；当奇数项的数量为奇数时，总和为奇数。由于度求和公式的一边是偶数 ${\displaystyle 2|E|}$，所以另一边的和必须有偶数个奇数项；也就是说，必须有偶数个奇数度数顶点。^[6]

此外，也可使用数学归纳法来证明度求和公式，^[3]或者透过从给定图中一次移除一条边，并对其端点的度数进行穷举法，以确定此移除对奇数度数顶点数量奇偶性的影响，从而直接证明奇数度数顶点的数量为偶数。^[18]

特殊类别的图

克莱布殊图（英语：Clebsch graph）是五度正则图，有偶数个顶点（16个），边数（40条）是五的倍数。

菱形十二面体是双正则图（英语：biregular graph），有六个度数为四的顶点和八个度数为三的顶点；6×4=8×3=24，亦为它的边数。

正则图

度求和公式意味着每个具有 ${\displaystyle n}$ 个顶点的 ${\displaystyle r}$-正则图有 ${\displaystyle nr/2}$ 条边。^[19]因为边的数量必须是整数，所以当 ${\displaystyle r}$ 是奇数时，顶点的数量必须是偶数。^[20] 此外，对于 ${\displaystyle r}$ 的奇数值，边的数量必须可被 ${\displaystyle r}$ 整除。^[21]

二部图与双正则图

一个二部图的顶点被分成两个子集，每条边的两个端点分别位于不同的子集中。同样地，透过双重计数的论证可以推断，在每个子集中，度数之和都等于图中边的数量。特别是，这两个子集的度数之和相等。^[22]对于双正则图（英语：Biregular graph），如果顶点被划分为 ${\displaystyle V_{1}}$ 和 ${\displaystyle V_{2}}$ 两个子集，并且子集 ${\displaystyle V_{i}}$ 中的每个顶点都具有度数 ${\displaystyle r_{i}}$，那么必然满足 ${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$；两者都等于边的数量。^[23]

无限图

只有一个奇顶点的无限图

握手引理之通常形式不适用于无限图，即使这些图只有有限数量的奇数度数顶点。例如，一条只有一个端点的无限路径图（英语：Path graph）图就只有一个奇数度数顶点，而不是偶数个。然而，可以利用末端（英语：End (graph theory)）（end）的概念来表述握手引理的一个版本。末端是指半无限路径（“射线（"rays"）”）的等价类，当存在第三条射线同时无限次使用两条射线中的顶点时，这两条射线被视为等价。一个末端的度数是它所包含的最大边不相交射线的数量，如果度数是有限且为奇数，则该末端是奇数的。更普遍地说，对于所有顶点都具有有限度数的图，无论末端是否具有无限度数，都可以将其定义为奇数或偶数。然后，在这样的图中，奇数顶点和奇数末端的数量加总后是偶数或无限个。^[24]

子图

根据 Gallai（英语：Tibor Gallai） 定理，任何图的顶点集 ${\displaystyle V}$ 都可以被划分为 ${\displaystyle V=V_{e}\cup V_{o}}$​，使得在两个由此产生的导出子图中，${\displaystyle G[V_{e}]}$ 的所有度数都是偶数，而 ${\displaystyle G[V_{o}]}$ 的所有度数都是奇数。根据握手引理，${\displaystyle |V_{o}|}$ 必须是偶数。此外，也可以找到具有许多顶点的偶数度数和奇数度数的导出子图。可以找到一个至少包含一半顶点的偶数度数导出子图，并且（在没有孤立顶点的图中）可以找到一个奇数度数导出子图，其满足 ${\displaystyle |V_{o}|/|V|>1/10000}$。^[25][26]

计算复杂度

主条目：PPA(复杂度)（英语：PPA(complexity)）

关于利用交换图（exchange graph）方法证明组合结构存在性的问题，人们对于如何有效地找到这些结构很感兴趣。例如，假设输入是一个三次图中的汉米顿循环；根据史密斯定理，存在第二个循环。那这个第二个循环能多快被找到呢？

Papadimitriou (1994) 研究了这类问题的计算复杂度，更广义地说，是在一个大型隐式定义图（英语：Implicit graph）中，当给定一个奇数度顶点时，寻找第二个奇数度顶点的问题。他定义了复杂度类 PPA 来概括这类问题；^[27]一个密切相关、定义在有向图上的类别 PPAD（英语：PPAD (complexity)），在算法赛局理论（英语：Algorithmic game theory）中引起了广泛关注，因为计算纳许均衡在计算上等同于此类别中最困难的问题。^[28]

被证明是 PPA 复杂度类别完备（complete）的计算问题包括与斯苯纳引理（英语：Sperner's lemma）^[29]相关的计算任务，以及根据Hobby–Rice 定理（英语：Hobby–Rice theorem）进行资源公平划分的问题。^[30]