握手引理：最樸素的圖論定理，卻威力無窮

 

「所有偉大的數學，都藏在最簡單的觀察裡。」

 

---

引言：一個派對上的問題

想像你參加一個派對，其中幾位賓客兩兩握了手。有人提出了一個問題：所有人握手次數的總和，是奇數還是偶數？

答案出乎意料地確定——永遠是偶數。

這個觀察雖然簡單，卻是圖論中最基礎、應用最廣的定理之一：握手引理（Handshaking Lemma）。從組合計數、演算法設計，到拓樸學中 Sperner 引理和 Brouwer 不動點定理的證明，握手引理無處不在。

---

基本定義

在進入定理之前，先確立幾個圖論的基本語言。

圖（Graph） $G=(V,E)$ 由兩個集合組成：頂點集 $V$（代表個體）和邊集 $E$（代表個體之間的關係）。每條邊連接兩個頂點。

一個頂點 $v$ 的度數（degree） $\mathrm{deg}(v)$，是指與 $v$

$v$ 相連的邊的條數。回到派對的例子：每個人就是一個頂點，兩人握手就是一條邊，每個人的 握手次數就是其度數。

---

定理敘述

維基百科 

握手引理：設 $G=(V,E)$ 為一個有限無向圖，則所有頂點的度數之和等於邊數的兩倍：

${\sum }_{v\in V}\mathrm{deg}(v)=2\mathrm{\mid }E\mathrm{\mid }$

直接推論：由於右側 $2\mathrm{\mid }E\mathrm{\mid }$ 必為偶數，左側的度數總和也是偶數。因此，度數為奇數的頂點，個數必定是偶數個（包含 0 個）。

---

證明：一個觀察就夠了

握手引理的證明極其簡短，核心是一個換個角度看問題的觀察。

證明：對每條邊 $e=\{u,v\}\in E$，它恰好對 u 的度數和 v 的度數各貢獻 1。因此，當我們把所有頂點的度數加總時，每條邊被計算了恰好兩次：

∑v∈Vdeg(v)=∑e∈E2=2∣E∣

整個證明只有兩行，卻蘊含著「換個計數順序」的精髓——先按頂點統 計，再意識到每條邊被重複計算，這種雙重計數（Double Counting）的思想在組合數學中反覆出現。

---

一個具體例子

設圖 (G) 有 5 個頂點，度數分別為：

deg(v1)=3,deg(v2)=2,deg(v3)=3,deg(v4)=1,deg(v5)=1

度數總和：

[3+2+3+1+1 = 10 = 2 ]

所以這個圖有 5 條邊。並且，度數為奇數的頂點（$v_1,v_3,v_4,v_5$）恰好有 4 個（偶數）。

---

重要推論

奇度頂點必為偶數個

這是握手引理最常用的推論：

推論：任何圖中，度數為奇數的頂點個數必定是偶數。

證明：

設奇度頂點集合為 $V_{\text{odd}}$，偶度頂點集合為 $V_{\text{even}}$，則：

${\sum }_{v\in V}\mathrm{deg}(v)=\underset{\text{奇數個奇數之和}}{\underbrace{{\sum }_{v\in V_{\text{odd}}}\mathrm{deg}(v)}}+\underset{\text{偶數}}{\underbrace{{\sum }_{v\in V_{\text{even}}}\mathrm{deg}(v)}}=2\mathrm{\mid }E\mathrm{\mid }$

右側為偶數，右側第二項為偶數，故左側第一項（奇數個奇數之和）必須也是偶數。奇數個奇數之和為偶數，當且僅當奇數的個數為偶數。∎

正則圖的邊數

$|E|=\frac{k\cdot |V|}{2}$

特別地，若 $k$ 為奇數，則 $\mathrm{\mid }V\mathrm{\mid }$

$|V|$ 必須是偶數（否則邊數不為整數）。

---

進階應用一：Euler 路徑的存在條件

Euler 路徑是一條恰好經過圖中每條邊一次的路徑，Euler 迴路則是起點與終點相同的 Euler 路徑。

定理（Euler，1736）：連通圖 (G) 存在 Euler 迴路，當且僅當每個頂點的度數均為偶數。存在 Euler 路徑（非迴路），當且僅當恰好有兩個奇度頂點。

為什麼與握手引理有關？因為在行走路徑時，每次「進入」一個頂點就需要「離開」，進出各消耗一條邊，這要求除了起點和終點外，每個頂點的度數必須是偶數。而握手引理保證奇度頂點必為偶數個——最少 0 個（Euler 迴路）或 2 個（Euler 路徑）。

柯尼斯堡七橋問題正是這個定理的歷史起源：七座橋對應的圖有 4 個奇度頂點，所以一筆畫（Euler 路徑）不存在。

---

進階應用二：Sperner 引理的證明

數學傳播 - pdf

這是握手引理最令人驚豔的應用之一，把組合計數與拓樸學聯繫起來。

Sperner 引理（1928）：將大三角形 $V_1{V}_2{V}_3$ 做三角剖分，並對所有頂點著三色（規則如下），則三色小三角形（三頂點顏色各不同）的數量為奇數，特別地至少有一個。

著色規則： 

• 大頂點 $V_i$ 著第 $i$ 色

• $V_i{V}_j$ 邊上的點只能著第 $i$ 或第 $j$ 色

• 內部頂點任意著三色之一

如何用握手引理？

構造半對偶圖 $T^{\mathrm{\prime }}$：每個小三角形（以及一個「無限外部面」）作為 $T^{\mathrm{\prime }}$ 的頂點，當兩個面之間的公共邊兩端分別標著顏色 1 和 2（稱為「12-邊」）時，就在 $T^{\mathrm{\prime }}$ 中連一條邊。

每個小三角形在 $T^{\prime }$ 中的度數如下：

小三角形類型	包含的 12-邊數	在 $T^{\mathrm{\prime }}$ 中的度數
三色（123）	1	1（奇數）
雙色（112 或 122）	2	2（偶數）
其他（111、333 等）	0	0（偶數）
外部無限面	$x$（見下）	$x$（奇數）

為何外部面度數為奇數？ 

$V_1{V}_2$ 邊上，頂點標號從 1 連續變化到 2，「換色」次數為奇數，故 12-邊數 $x$ 為奇數。

設三色三角形數量為 $\mathrm{\ell }$，由握手引理，$T^{\mathrm{\prime }}$ 中所有頂點度數之和為偶數：

$\mathrm{\ell }\cdot 1+(\text{偶度頂點的度數和})+x=2\mathrm{\mid }{E}_{T^{\mathrm{\prime }}}\mathrm{\mid }$

因此：

$\mathrm{\ell }+x\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)⟹\mathrm{\ell }\equiv x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}2)$

$\mathrm{\ell }$

$\ell$ 為奇數，至少為 1。∎ () 為奇數，至少為 1。∎ 

這個論證的美妙之處在於：從「計數 12-邊」這個純粹的組合操作，竟然推出了一個幾何結構（三色三角形存在）的深刻結論。

---

進階應用三：通往 Brouwer 不動點定理

維基百科

Sperner 引理不只是一個孤立的組合命題——它是 Brouwer 不動點定理的基石。

Brouwer 不動點定理：若 $f:D\to D$ 是凸緊集到自身的連續映射，則存在不動點 $x^{\ast }$ 使得 $f(x^{\ast })=x^{\ast }$。

證明策略：

對三角形 $T$ 做越來越細的三角剖分（第 $n$ 級，網格大小 $\frac{1}{n}$），利用映射 $f$ 的重心座標定義 Sperner 著色，每次都由 Sperner 引理保證至少一個三色三角形存在。令 $n\to \mathrm{\infty }$，由緊緻性取收斂子列，極限點 $p^{\ast }$ 即為不動點。

整個邏輯鏈如下：

握手引理⇒Sperner 引理⇒Brouwer 不動點定理⇒Nash 均衡存在性

一個關於度數之和的初等觀察，最終撐起了現代賽局理論的核心定理——這正是數學基礎研究的力量。

---

握手引理的不同面貌

應用領域	握手引理的角色	具體應用
圖論	基本工具	Euler 路徑存在條件
組合數學	雙重計數	證明 Sperner 引理
拓樸學	間接基石	證明 Brouwer 不動點定理
電腦科學	演算法分析	網路協定的握手設計、圖遍歷演算法
賽局理論	基礎支撐	Nash 均衡的存在性

結語：一條邊，兩個端點

握手引理的精髓可以濃縮成一句話：每條邊有兩個端點。

這個觀察平凡到幾乎讓人懷疑它的用處，但正是這種「換個角度數同一件事」的思維，>支撐起了從 Euler 的七橋問題到 Nash 均衡的整座數學大廈。

數學的美，往往就藏在這樣的簡單觀察裡——樸素，卻威力無窮。

---

本文涵蓋了握手引理的定義、證明、推論，以及在 Euler 路徑、Sperner 引理與 Brouwer 不動點定理中的應用，適合對數學有基本興趣的讀者閱讀。