在圖論 中，握手引理 （英語：handshaking lemma ）為在每個有限無向圖 中，頂點 鄰接奇數個邊 的數量有偶數個。也可以說，度數 為奇數的頂點有偶數個。例如，在某派對上大家互相握手，則「跟奇數個人握手的人」有偶數個。[ 1] 度求和公式 （英語：degree sum formula ）推導而得，內容為無向圖中所有頂點的度數 （鄰接到該頂點的邊數）總和為該圖邊數的兩倍。上面的兩個結果都由 李昂哈德‧歐拉 （1736 ）柯尼斯堡七橋問題 的論文上證明，也就是圖論研究的起點。[ 2]
此圖中，有偶數個頂點（編號為2、4、5、6的四個頂點）的度數為奇數。所有六個頂點的度數總和為 2+3+2+3+3+1=14，是邊數的兩倍。 除了後來催生一筆畫問題 的柯尼斯堡七橋問題之外，度求和公式的其他應用還包括了某些組合結構的證明。例如，在斯苯納引理 爬山問題 的證明中，該公式的幾何特性經常出現。複雜度類 PPA 隱式定義圖
在無向圖 中，包含一系列的頂點 與連接無序 頂點對的邊。在任何的圖中，頂點
v
{\displaystyle v}
deg
(
v
)
{\displaystyle \deg(v)}
v
{\displaystyle v}
環 的圖，為了符合握手引理，每個環應該對其端點的度數貢獻兩單位（即有環的頂點本身度數加二）。[ 3]
deg
(
v
)
{\displaystyle \deg(v)}
[ 4] [ 5] [ 5] [ 6]
度求和公式指出：
∑
v
∈
V
deg
v
=
2
|
E
|
,
{\displaystyle \sum _{v\in V}\deg v=2|E|,}
V
{\displaystyle V}
E
{\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 立方圖
G
{\displaystyle G}
u
v
{\displaystyle uv}
漢米頓迴圈 數量必為偶數；這些迴圈恰好經過每個頂點一次。湯瑪森 (1978) harvtxt模板錯誤: 無指向目標: CITEREF湯瑪森1978 (幫助 ) 則是利用基於握手引理的證明，將此結果推廣到所有頂點都具有奇數度數的圖。湯瑪森定義一個交換圖
H
{\displaystyle H}
G
{\displaystyle G}
u
{\displaystyle u}
u
v
{\displaystyle uv}
p
2
{\displaystyle p_{2}}
p
1
{\displaystyle p_{1}}
p
1
{\displaystyle p_{1}}
p
1
{\displaystyle p_{1}}
p
2
{\displaystyle p_{2}}
H
{\displaystyle H}
對稱關係 ，因此
H
{\displaystyle H}
p
{\displaystyle p}
w
{\displaystyle w}
H
{\displaystyle H}
p
{\displaystyle p}
p
{\displaystyle p}
u
{\displaystyle u}
p
{\displaystyle p}
u
v
{\displaystyle uv}
H
{\displaystyle H}
deg
(
w
)
−
1
{\displaystyle \deg(w)-1}
p
{\displaystyle p}
u
v
{\displaystyle uv}
deg
(
w
)
−
2
{\displaystyle \deg(w)-2}
H
{\displaystyle H}
G
{\displaystyle G}
u
v
{\displaystyle uv}
[ 13]
握手引理（或度求和公式）在數學中也用於證明其他幾項結果。其中包括：
經過斯苯納染色的三角形分割圖，其中陰影部分標示出具所有三種顏色的頂點之小三角形。 斯苯納引理 不動點定理 、求根演算法 ，與公平分配賽局 。其中一個證明方法是構造一個交換圖，其頂點是這些（大大小小）的三角形且其邊連接的是共享某兩種特定顏色的兩個頂點的三角形對。這個交換圖中，大三角形的度數必然是奇數，具所有三種顏色的小三角形的度數也為奇數，而其他小三角形的度數則為偶數。根據握手定理，具所有三種顏色的小三角形的數量必為奇數，因此至少存在一個這樣的小三角形。[ 14] 爬山問題 爬山問題 指出，對於單位區間 上的良態 ，且區間兩端點函數數值相等的函數，可以協調從兩個區間端點同時出發的點的運動（如動畫所示），使它們在區間內的某點相遇，並且在整個運動過程中始終保持在函數值相等的位置。該問題的證明方法之一，需要一個近似原始函數的，具相同極值點的分段線性函數 單位正方形 中單一點的座標來參數化兩個移動點的位置。最後，證明兩個點的可移動位置形成一個嵌入在此單位正方形中的有限圖，而該圖中只有起始位置及其反向位置為奇頂點。根據握手定理，這兩個位置屬於圖中的同一個連通元件 ，因此從一個位置到另一個位置的路徑必然會經過所需的相遇點。[ 15] 重構猜想 是關於從移除單一頂點所形成的子圖多重集 來唯一確定圖結構的問題。給定這些資訊，度求和公式可以用來恢復原始圖中的邊數以及每個頂點的度數，而從中可以判斷給定圖是否為正則圖 。如果是，則可以通過為所有度數過低的子圖頂點添加新鄰居，從任何一個刪除頂點的子圖中唯一地確定該正則圖。因此，所有正則圖都可以被重構。[ 16] 六貫棋 （Hex）是一種由兩名玩家進行的遊戲。玩家輪流在由六邊形 方格組成的平行四邊形 棋盤上放置自己顏色的棋子，直到其中一名玩家的棋子從棋盤的一邊連接到另一邊，形成一條連續的路徑為止。這個遊戲永遠不會出現平局：當棋盤完全被棋子填滿時，其中一名玩家必然已經形成了一條獲勝路徑。證明這一點的方法之一是從一個已經下滿棋子的棋盤構造一個圖。在這個圖中，六邊形的角點是頂點，而分隔兩種玩家顏色的六邊形邊緣則是邊。這個圖在棋盤的四個角點有四個奇頂點，其他地方的頂點則都是偶數。因此，它必然包含一條連接兩個角點的路徑，這條路徑的其中一側必然屬於其中一名玩家的獲勝路徑。[ 17]
歐拉證明度求和公式時使用了雙重計數 的技巧：他以兩種不同的方式，計算了關聯對
(
v
,
e
)
{\displaystyle (v,e)}
e
{\displaystyle e}
v
{\displaystyle v}
v
{\displaystyle v}
deg
(
v
)
{\displaystyle \deg(v)}
deg
(
v
)
{\displaystyle \deg(v)}
v
{\displaystyle v}
2
|
E
|
{\displaystyle 2|E|}
關聯矩陣 [ 6]
對於圖而言，握手引理是度求和公式的直接推論。[ 9] 奇偶性 不受總和中偶數項的影響；當奇數項的數量為偶數時，總和為偶數；當奇數項的數量為奇數時，總和為奇數。由於度求和公式的一邊是偶數
2
|
E
|
{\displaystyle 2|E|}
[ 6]
此外，也可使用數學歸納法 來證明度求和公式，[ 3] 窮舉法 ，以確定此移除對奇數度數頂點數量奇偶性的影響，從而直接證明奇數度數頂點的數量為偶數。[ 18]
克萊布殊圖 是五度正則圖，有偶數個頂點（16個），邊數（40條）是五的倍數。
菱形十二面體 是
雙正則圖 ，有六個度數為四的頂點和八個度數為三的頂點；6×4=8×3=24，亦為它的邊數。
度求和公式意味著每個具有
n
{\displaystyle n}
r
{\displaystyle r}
正則圖 有
n
r
/
2
{\displaystyle nr/2}
[ 19]
r
{\displaystyle r}
[ 20]
r
{\displaystyle r}
r
{\displaystyle r}
[ 21]
一個二部圖 的頂點被分成兩個子集，每條邊的兩個端點分別位於不同的子集中。同樣地，透過雙重計數的論證可以推斷，在每個子集中，度數之和都等於圖中邊的數量。特別是，這兩個子集的度數之和相等。[ 22] 雙正則圖
V
1
{\displaystyle V_{1}}
V
2
{\displaystyle V_{2}}
V
i
{\displaystyle V_{i}}
r
i
{\displaystyle r_{i}}
|
V
1
|
r
1
=
|
V
2
|
r
2
{\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}
[ 23]
只有一個奇頂點的無限圖 握手引理之通常形式不適用於無限圖，即使這些圖只有有限數量的奇數度數頂點。例如，一條只有一個端點的無限路徑圖 末端 [ 24]
根據 Gallai
V
{\displaystyle V}
V
=
V
e
∪
V
o
{\displaystyle V=V_{e}\cup V_{o}}
導出子圖 中，
G
[
V
e
]
{\displaystyle G[V_{e}]}
G
[
V
o
]
{\displaystyle G[V_{o}]}
|
V
o
|
{\displaystyle |V_{o}|}
孤立頂點 的圖中）可以找到一個奇數度數導出子圖，其滿足
|
V
o
|
/
|
V
|
>
1
/
10000
{\displaystyle |V_{o}|/|V|>1/10000}
[ 25] [ 26]
關於利用交換圖（exchange graph）方法證明組合結構存在性的問題，人們對於如何有效地找到這些結構很感興趣。例如，假設輸入是一個三次圖中的漢米頓迴圈；根據史密斯定理，存在第二個迴圈。那這個第二個迴圈能多快被找到呢？
Papadimitriou (1994) 研究了這類問題的計算複雜度 ，更廣義地說，是在一個大型隱式定義圖 複雜度類 PPA [ 27] PPAD 演算法賽局理論 納許均衡 在計算上等同於此類別中最困難的問題。[ 28]
被證明是 PPA 複雜度類別完備 （complete）的計算問題包括與斯苯納引理 [ 29] Hobby–Rice 定理 [ 30]
^ Hein, James L. " Example 3: The Handshaking Problem" ISBN 9781284070408 ^ 2.0 2.1 Euler, L. , Solutio problematis ad geometriam situs pertinentis , Commentarii Academiae Scientiarum Imperialis Petropolitanae, 1736, 8 : 128–140 [2025-07-16 ] , （原始内容存档 于2024-12-09） Biggs, N. L.; Lloyd, E. K.; Wilson, R. J., Graph Theory 1736–1936, Oxford University Press, 1976 ^ 3.0 3.1 Gunderson, David S., Handbook of Mathematical Induction: Theory and Applications , CRC Press: 240, 2014, ISBN 9781420093650 ^ Hein, James L., Example 3: The Handshaking Problem , Discrete Structures, Logic, and Computability, Jones & Bartlett Publishers: 703, 2015, ISBN 9781284070408 ^ 5.0 5.1 Higgins, Peter M., Mathematics for the Curious , Oxford University Press: 201, 1998, ISBN 9780192880727 ^ 6.0 6.1 6.2 Biggs, Norman L., 15.3: Degree , Discrete Mathematics, Oxford University Press: 181–182, 2002, ISBN 9780198507178 ^ West, Douglas B., 1.3.3. Theorem. (Degree-Sum Formula), Introduction to Graph Theory 2nd, Prentice Hall: 26, 1996, ISBN 9780132278287 ^ Loehr, Nicholas, 3.31. Theorem: Degree-Sum Formula for Digraphs , Bijective Combinatorics, CRC Press: 106, 2011, ISBN 9781439848869 ^ 9.0 9.1 Jukna, Stasys, Proposition 1.7, Extremal Combinatorics, Texts in Theoretical Computer Science. An EATCS Series, Springer: 9, 2011, ISBN 978-3-642-17363-9doi:10.1007/978-3-642-17364-6 ^ Ray, Santanu Saha, Theorem 2.2, Graph Theory with Algorithms and its Applications in Applied Science and Technology , Springer: 16, 2012, ISBN 9788132207504 ^ Christofides, Nicos, Worst-case analysis of a new heuristic for the travelling salesman problem (PDF) , Report 388, Graduate School of Industrial Administration, CMU, 1976, （原始内容存档 (PDF) 于July 21, 2019） ^ Cameron, Kathie; Edmonds, Jack, Some graphic uses of an even number of odd nodes , Annales de l'Institut Fourier 49 (3): 815–827 [2025-07-16 ] , MR 1703426 doi:10.5802/aif.1694 存档 于2016-03-03） ^ Thomason, A. G., Hamiltonian cycles and uniquely edge colourable graphs, Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics 3 : 259–268, 1978, ISBN 978-0-7204-0843-0MR 0499124 doi:10.1016/S0167-5060(08)70511-9 ^ Aigner, Martin; Ziegler, Günter M., Section 28.6: Sperner's Lemma, Proofs from THE BOOK ISBN 978-3-662-57264-1MR 3823190 doi:10.1007/978-3-662-57265-8 ^ Goodman, Jacob E.; Pach, János; Yap, Chee-K., Mountain climbing, ladder moving, and the ring-width of a polygon (PDF) , 美國數學月刊 , 1989, 96 (6): 494–510, JSTOR 2323971 MR 0999412 doi:10.2307/2323971 ^ Lauri, Josef; Scapellato, Raffaele, Topics in Graph Automorphisms and Reconstruction , London Mathematical Society Lecture Note Series 432 2nd, Cambridge University Press: 105–106, 2016, ISBN 978-1-316-61044-2MR 3496604 doi:10.1017/CBO9781316669846 ^ Gale, David, The game of Hex and the Brouwer fixed-point theorem, 美國數學月刊 , 1979, 86 (10): 818–827, JSTOR 2320146 MR 0551501 doi:10.1080/00029890.1979.11994922 ^ Neto, Antonio Caminha Muniz, An Excursion through Elementary Mathematics, Volume III: Discrete Mathematics and Polynomial Algebra, Problem Books in Mathematics, Springer: 132 , 562 , 2018, ISBN 9783319779775 ^ Aldous, Joan M.; Wilson, Robin J., Theorem 2.2 , Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag: 44 , 2000, ISBN 978-1-85233-259-4 ^ Wallis, W. D., Section 7.1, Introduction to Graphs, Corollary 1 , A Beginner's Guide to Discrete Mathematics 2nd, Springer: 219, 2011, ISBN 9780817682866 ^ Clark, John; Holton, Derek Allan, Problem 1.4.6 , A First Look at Graph Theory, Allied Publishers: 16, 1995, ISBN 9788170234630 ^ Lovász, László, Combinatorial Problems and Exercises 2nd, Elsevier: 281, 2014, ISBN 9780080933092 ^ Pisanski, Tomaž; Servatius, Brigitte, 2.3.4: Semiregular Bipartite Graphs , Configurations from a Graphical Viewpoint, Birkhäuser Advanced Texts: Basler Lehrbücher, New York: Birkhäuser/Springer: 35, 2013, ISBN 978-0-8176-8363-4MR 2978043 doi:10.1007/978-0-8176-8364-1 ^ Bruhn, Henning; Stein, Maya, On end degrees and infinite cycles in locally finite graphs, Combinatorica 27 (3): 269–291, MR 2345811 S2CID 8367713 doi:10.1007/s00493-007-2149-0 ^ Ferber, Asaf; Krivelevich, Michael, Every graph contains a linearly sized induced subgraph with all degrees odd, Advances in Mathematics, 2022, 406 , MR 4448268 arXiv:2009.05495 doi:10.1016/j.aim.2022.108534 ^ Honner, Patrick, What a Math Party Game Tells Us About Graph Theory , Quanta, 2022-03-24 [2022-03-27 ] , （原始内容存档 于2025-05-25） ^ Papadimitriou, Christos H., On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (3): 498–532, MR 1279412 doi:10.1016/S0022-0000(05)80063-7 ^ {{citation|first1=Xi|last1=Chen|first2=Xiaotie|last2=Deng|contribution=Settling the complexity of two-player Nash equilibrium|title=Proc. 47th Symp. Foundations of Computer Science
^ Grigni, Michelangelo, A Sperner lemma complete for PPA, Information Processing Letters 77 (5–6): 255–259, MR 1818525 doi:10.1016/S0020-0190(00)00152-6 ^ Filos-Ratsikas, Aris; Goldberg, Paul W., Consensus halving is PPA-complete, Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (编), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 ISBN 978-1-4503-5559-9S2CID 8111195 arXiv:1711.04503 doi:10.1145/3188745.3188880
![{\displaystyle G[V_{e}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d556254cec3bcb9535d72556bbe121017ab7a64)
![{\displaystyle G[V_{o}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57cf81ced515e732479f4edfff7896386ae77ff5)
