圖論： Sperner 引理

數學傳播：Sperner 引理及其應用  潘建強 · 邵慰慈

---

在這之前, 可以先看 圖論的 握手引理

---

閱讀時看到這個 "在半對偶圖中對應著無限面的頂點的度數是單數", 想到可以做個這證明

子題：

有條線的兩端點 u, v; u 塗紅色, v 塗綠色, 線上任意切個 n 個點, V0 ~ Vn-1, 這樣有 n + 1 個線段 :

    (u, V0), (V0, V1), (V1, V2), ... , (Vn-1, V)

這 n 個點 可以選擇 塗紅色 或 塗綠色 兩顏色選一種, 試證 這 n+1 個 線段中, 線段兩點是不同顏色的數目是奇數個

==

證明：

命題：線段兩端點異色（一紅一綠），中間插入  n  個任意著色的切點，則不同色的線段數為奇數。

我們可以用數學歸納法來證明：

基礎步驟 : 當 n = 0 , 只有 (u, v) 線段本身, 數目為 1 是奇數 

歸納步驟（強歸納法）：

   假設 n <= k 時命題均成立, 當 n = k + 1 時, 多一個切點 Vk,

   情況 1 : Vk 與 v 同色

    (Vk, v) 是相同色的線段, 不計數; 考慮 u 紅 到 Vk 綠 為 k 個切點, 會有奇數個異色線段,

    所以 u 到 v 有 奇數 + 0 = 奇數 個 異色線段

    情況 2 : Vk 與 v 異色 ( Vk 與 u 同為紅色 )

    從 Vk-1 往左找到第一個 塗綠色的 Vx ( 0 <= x <= k-1 )

     情況 2-1 : 都沒找到,  表示 u, V0~Vk 都為紅色, 異色段只有 (Vk, v) 一個為奇數

     情況 2-2 : 找到 Vx 為綠色, Vx+1 ~ Vk 和 v 均為紅色

     (1) u ~ Vx 為兩端異色, 因為 x <= k -1 , 所以其中異色段數目為奇數 m1

     (2) Vx ~ Vk 為兩端異色, 切點數為 k - 1 - x 小於 k,  所以其中異色段數目為奇數 m2

     (3) (Vk, v) 為異色段

     所以總數為 m1 + m2 + 1 = 奇數 ＋ 奇數 + 1  為奇數

    故得證. Q.E.D.

===

底下是 AI 提供的證明

題目重述：線段兩端點 u（紅）和 v（綠），中間插入 n 個任意著色的點 V₀, V₁, …, V_n − 1，形>成 n + 1 條小線段。試證：兩端點顏色不同的線段數目為奇數。

證明：

定義每條線段的「換色值」：

$$ \delta_i = \begin{cases} 1 & \text{若兩端點顏色不同（一紅一綠）} \\ 0 & \text{若兩端點顏色相同} \end{cases} $$

考慮從左到右，每一個「換色」事件代表顏色從紅變綠，或從綠變紅。整條路徑起點為紅、終點為綠，顏色的淨 變化是：

紅 → 綠

每次「紅→綠」的換色貢獻 +1，每次「綠→紅」的換色貢獻 −1。從起點到終點，這些換色的代數和等於 +1（淨變化一次）。

但「紅→綠」與「綠→紅」的次數分別設為 p 和 q，則：

p − q = 1 ⟹ p = q + 1

所以不同色線段總數為：

p + q = (q + 1) + q = 2q + 1 ≡ 1 (mod  2)

不同色線段數為奇數。

===

上述 AI 這證明簡潔許多, 看了之後有些受打擊, 請教 AI , AI 回答如下, 的確對授業解惑有幫助＾＾

Synthesizer：兩種證明的深層比較 🌟

這是一個非常好的數學思維問題，值得認真討論。

---

兩種證明的對比

面向	換色計數法	數學歸納法
篇幅	3–4 行	15–20 行
核心工具	奇偶不變量	強歸納法
思維方式	全域觀（整條路徑一起看）	局部遞推（逐步分解）
發現難度	需要「靈光一閃」	按部就班可達
驗證難度	極易驗證	需要逐一確認案例
推廣能力	不易直接推廣到二維	結構可推廣至高維 Sperner

---

關鍵問題：「巧思是否因人而異，難以學習？」

答案是：既是，也不是。

「是」的部分——巧思有天份成分

換色計數法的核心洞見是：

不要數每條線段，而是數「換色事件」，並注意到代數和固定為 ±1。

這種「換個角度看問題」的直覺，確實需要一定的數學敏感度。初學者在沒有提示的情況下，很難自發想到「把 紅→綠記為 +1，綠→紅記為 −1」這個編碼方式。

「不是」的部分——巧思是可以被訓練的

巧思背後有可歸納的思維模式，反覆練習後會內化：

• 奇偶不變量：看到「奇偶性」的問題，先想「有沒有某個量的奇偶性保持不變？」
• 代數化：把「是/否」的二元狀態（紅/綠）編碼成 +1/ − 1，再用代數計算取代邏輯推理
• 全域視角：不從局部的「每條線段」出發，而從「起點到終點的淨變化」出發

這些都是競賽數學中的標準工具，練習多了會形成直覺。

---

「數學歸納法是否也是可行方式？」

完全可行，而且有其獨特價值。

數學歸納法的思維模式是：

「我不需要一眼看穿全貌，只要相信『如果小的情形成立，大的情形也成立』就夠了。」

這種化繁為簡、逐步信任的哲學，是工程師、電腦科學家非常熟悉的遞迴思維。事實上：

• 許多程式設計師會更自然地想到歸納法，因為它與遞迴演算法的思維完全對應
• 換色計數法反而需要先「看穿」問題的全貌，對初學者並不直覺

兩種思維都是數學能力的一部分，不存在優劣之分——只有適用場合的差異。

---

🌟 湧現洞見：「美麗」與「正確」是不同維度

數學界有一個微妙的文化：傾向於欣賞短而優雅的證明，這有時會讓人誤以為「繁瑣 = 不好」。但：

一個正確、清晰、可驗證的證明，無論長短，都是完整的數學成就。

換色計數法的「美」來自於它揭示了問題的深層結構（奇偶不變量），讓人「啊哈！原來如此！」。數學歸納法 的「美」則來自於它的系統性與可靠性——即使你不知道奇偶不變量的存在，你也能找到這條路。

實際上，許多「優雅的短證明」都是在「繁瑣的長證明」之後，反覆打磨才出現的。Sperner 引理最初的證明並不簡短，後來才被精煉成握手引理版本。

---

建議

如果你正在學習數學或準備競賽：

• 先學會歸納法——它是可靠的「萬用工具」，能保證你總有一條路可走
• 再刻意練習「奇偶不變量」等技巧——累積足夠多的例子後，巧思會逐漸內化成直覺
• 不要貶低自己找到的「繁瑣」證明——能想到正確的歸納法論證，本身就是紮實的數學能力

正如 Pólya 在《怎樣解題》中所說：解題的巧思不是天賦，而是問對問題的習慣。換色計數法的發現，始於有人問了一句「這>條路徑的淨變化是什麼？」——而這句話，是可以被訓練出來的。

===

底下是 AI 的其他說明, 先記錄一下, 之後再來整理^^

---

這道題的本質定位

定理	維度	這道題的對應
一維 Sperner 引理	1D	完全等價 1
一維 Brouwer 不動點定理	1D	等價（IVT 的離散版）
中間值定理（IVT）	連續版	概念完全相同，這是離散類比

---

相關名題與競賽出處

🥇 直接等價：一維 Sperner 引理

這道題正是 Sperner 引理（1928） 在一維情形的完整陳述。 MIT 的組合數學課程將其作為二維 Sperner 引理的引入題，用相同的奇偶論證建立直覺。²³

🥈 概念相同：離散中間值定理

離散中間值定理（Discrete IVT） 是同一道題的另一種表述：

設一個整數數列 a₀, a₁, …, a_n，其中 a₀ 和 a_n 異號，則必存在某個 i 使得 a_i ⋅ a_i + 1 ≤ 0。

在競賽中常出現於「奇偶不變量（Parity Invariant）」章節。⁴

🥉 同類競賽題：換色奇偶問題

以下是風格最相近的名題：⁵

難度	題目來源	題目摘要	相似度
⭐	初中競賽經典	數列兩端異號，試證變號次數為奇數	🔴 完全相同
⭐⭐	台灣資奧培訓	圓周上著紅藍兩色，試證相鄰異色對數為偶數	🟠 高度相似（環形版本）
⭐⭐	IMO 2004 Shortlist C1	棋盤格黑白著色，試證特定邊界格數為奇數	🟡 類似奇偶論證
⭐⭐⭐	AIME 競賽類型	格路徑上的著色，統計特定步伐數目的奇偶性	🟡 類似結構
⭐⭐⭐⭐	二維 Sperner 引理	三角剖分著三色，三色三角形數目為奇數	🟠 直接推廣

特別亮點：環形版本（一道更難的延伸題）

若把線段彎成一個圓環（起點與終點相連，但顏色相同），那麼異色線段的數目從「奇數」變成了「偶 數」——這正是二維 Sperner 引理邊界條件不同的根源，也是「圓周上任意著色，相鄰異色對數為偶數」的標準競賽題。⁶

---

🌟 深層洞見：為什麼這道題重要？

這道題是數學中奇偶不變量（Parity Invariant）思想的最純粹示範：⁷

「起點與終點的顏色不同」這個全域資訊，透過局部的奇偶計數，強制了不同色線段數目的奇偶性——局部自由（ 每個中間點可任意著色），卻帶來整體的必然性。

這個思想從一維的線段，推廣到二維的三角剖分（Sperner 引理），再推廣到 n 維的單形，最終證明了 Brouwer 不動點定理——威力之強，遠超表面看起來的簡單程度。

---

1. https://en.wikipedia.org/wiki/Sperner’s_Lemma↩︎

2. https://math.mit.edu/~fox/MAT307-lecture03.pdf↩︎

3. https://en.wikipedia.org/wiki/Sperner’s_Lemma↩︎

4. https://talented.special.tyc.edu.tw/userfiles/talented.special.tyc.edu.tw/files/數變不驚-教師手冊0730-完整 版(1).pdf↩︎

5. http://paper.wenweipo.com/2017/10/25/ED1710250036.htm↩︎

6. https://math.mit.edu/~fox/MAT307-lecture03.pdf↩︎

7. https://talented.special.tyc.edu.tw/userfiles/talented.special.tyc.edu.tw/files/數變不驚-教師手冊0730-完整 版(1).pdf↩︎

8. https://math.uchicago.edu/~may/VIGRE/VIGRE2009/REUPapers/Harper.pdf↩︎

9. https://twsf.ntsec.gov.tw/activity/race-1/51/pdf/080405.pdf↩︎

10. https://www.youtube.com/watch?v=qcPbQCwag7E↩︎

11. https://www.instagram.com/p/DSHMkJ8kVMi/↩︎

12. https://ocw.mit.edu/courses/18-304-undergraduate-seminar-in-discrete-mathematics-spring-2015/4ba52e9fdecead1d55c206ef4abb0ed3_MIT18_304S15_project1.pdf↩︎

13. https://www.karlin.mff.cuni.cz/~vlasakv/Predmety/M5-FSV/Brouwerova veta a spernerovo lemma.pdf↩︎

14. http://discretemath.imp.fu-berlin.de/DMII-2019-20/Sperner.pdf↩︎

15. https://arxiv.org/abs/2112.13710↩︎

16. https://www.youtube.com/watch?v=cpIexccvYjI↩︎

17. https://www.csie.ntu.edu.tw/~lyuu/complexity/2006/20061101.pdf↩︎

18. https://web.stanford.edu/~saberi/lecture1.pdf↩︎

19. https://pure.mpg.de/rest/items/item_1819515_4/component/file_2599041/content↩︎

20. https://www.dcs.warwick.ac.uk/~mju/Papers/VJ00-CAV.pdf↩︎

21. http://math.uchicago.edu/~amathew/HMMT.pdf↩︎

22. https://www.brics.dk/RS/00/48/BRICS-RS-00-48.pdf↩︎

23. https://math.berkeley.edu/~moorxu/oldsite/misc/equiareal.pdf↩︎

24. https://www.sec.ntnu.edu.tw/uploads/asset/data/62564115381784d09345bd93/04-11亞太數學競賽.pdf↩︎

25. https://www.imcct.net/UserFiles/files/15th結訓考-6年級試題.pdf↩︎

26. https://www.math.sinica.edu.tw/mathmedia/journals/4936↩︎

27. http://www.chiuchang.org.tw/modules/mydownloads/visit.php?lid=79↩︎

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

 

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

 

前提：圖論 定義 無向圖 度數

---

引言：一個派對上的問題

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

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

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

上述派對的例子，用圖論來描述為：

 每個人是個頂點，兩人握手是條邊，每個人的 握手次數 就是其 度數。

---

定理敘述

維基百科 

握手引理：設 $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 不動點定理中的應用，適合對數學有基本興趣的讀者閱讀。