基本介紹
定義,套用,例舉推證,頂點的度數與握手定理,Sperner引理的套用,推論,握手定理與哈密頓圖,握手定理和Sperner引理,
定義
給定無向圖𝐺 =(𝑉,𝐸)，有∑deg𝐺(𝑣) = 2|𝐸|。
套用
例舉推證
例：在宴會中，有10位嘉賓，每位嘉賓在宴會握手2次，求宴會總共握手幾次。
解：根據 握手總次數S= nx/2，S=10
註：每人握手次數即一個人在握手中總共其他人握手幾次，由於握手是雙向的，A與B握手，同時也是說B在與A握手，如果單純計算是10*2=20次，而其中握手是由於雙向重複的，實際握手次數需要除以2。
頂點的度數與握手定理
--------------------------------------------------------------------------------
1．頂點的度數
定義14.4 設G=為一無向圖，v∈V，稱v作為邊的端點次數之和為v的度數，簡稱為度，記做 dG(v)，在不發生混淆時，簡記為d(v).設D=為有向圖，v∈V，稱v作為邊的始點次數之和為v的出度，記做(v)，簡記作d+(v).稱v作為邊的終點次數之和為v的入度，記做(v)，簡記作d-(v)，稱d+(v)+d-(v)為v的度數，記做d(v).
--------------------------------------------------------------------------------
2．握手定理
定理14.1(握手定理) 設G=為任意無向圖，V={v1,v2,…,vn}，|E|=m，則
所有頂點的度數和=2m
證 G中每條邊(包括環)均有兩個端點，所以在計算G中各頂點度數之和時，每條邊均提供2度，當然，m條邊，共提供2m度。
定理14.2(握手定理) 設D=為任意有向圖，V={v1,v2,…,vn}，|E|=m，則
所有頂點的度數和=2m，且出度=入度=m.
本定理的證明類似於定理14.1
握手定理的推論 任何圖(無向的或有向的)中，奇度頂點的個數是偶數。
證 :
所有頂點的度數和(2m=偶數)=偶度頂點的度數之和(偶數)+奇度點的頂點度數之和，所以
偶度頂點的頂點度數之和是一個偶數，而奇數個奇數為奇數，故奇數點的個數必為偶數。
握手定理也稱為圖論的基本定理，圖中頂點的度數是圖論中最為基本的概念之一。
Sperner引理的套用
（1）不動點（Fix point）
Δ是平面上一個三角形。f:Δ→Δ連續：
（2）HEX game
HEX game：兩個玩家，分別用紅色和藍色對平面上一個內部被分割為若干三角形的正方形著色。玩家從一個正方形頂點開始著色（兩個玩家開始的頂點不在對角線上），每次著色一個頂點，下一次著色的頂點必須與上一次著色的頂點相鄰，先著色到對角線上另一個頂點的玩家獲勝。
HEX game
命題：一定有一個獲勝者。
證明：令R=著色為紅色的頂點集合，B=著色為藍色的頂點集合。
對頂點v用數字標記：
1：如果頂點
且有一條從a→v的純紅色路徑
2：如果頂點
且有一條從b→v的純藍色路徑
3：其他頂點
若此命題不成立，則頂點c,d都被標記為3。由Sperner引理知，一定有一個包含三個不同標記1、2、3的三角形。如果c,d都被標記為3，則這個三角形如圖所示。但這顯然違反了標記規則，故c被標記為1和d被標記為2至少有一個成立。所以RED與BLUE之一會獲勝。
包含三個標記的三角形
推論
無向圖中，度數為奇數的點一定是有偶數多個。
握手定理與哈密頓圖
證明：(Thomason 1978)
圖𝐺是3-正則圖，𝑒 = {𝑣1, 𝑣2}是一條固定的邊，不失一般性，假設原圖中有含有𝑒的哈密頓迴路。
構造圖𝐺′= (𝑉′, 𝐸)
· 𝑉′中的每一點，代表一條從𝑣1開始，以𝑒為第一條邊的哈密頓路徑（由前提假設知𝑉′非空）
構造𝐸'：
構造G'、E'
𝑣𝑝 ∈ 𝑉' 代表哈密頓路徑P
𝑣𝑛在𝐺中度數為3，故必存在
滿足𝑣𝑘, 𝑣𝑛 ∈𝐸(𝐺)；
𝑃′= 𝑣1 𝑣2 … 𝑣𝑘 𝑣𝑛 𝑣(𝑛−1) … 𝑣(𝑘+1)是哈密頓路徑。𝑣𝑝' ∈ 𝑉′；
{𝑣𝑝, 𝑣𝑝'} ∈ 𝐸'
𝐸'中任意𝑣𝑝的度數至多為2：
𝑑𝑒g(𝑣𝑝) = 1若且唯若原始用到的哈密頓路徑實際上是圖𝐺𝐺中一個哈密頓迴路。
握手定理和Sperner引理
已知平面上的一個三角形ABC，它被任意劃分為若干小的不重疊的三角形。用紅、黃、藍依次對A、B、C三個頂點著色。對其餘頂點：BC邊上的點用黃或藍著色；AB上的點用紅或黃著色；AC邊上的點用紅或藍著色。其他內部頂點任意著色。
Sperner引理：必然存在一個三個頂點都不同色的三角形。
證明：構造圖G=(V,E)。
V:每個閉合的連續平面（小三角形）抽象為一個點，外面的開放平面也抽象為一個點，取名為v。
E:兩個頂點之間有一條邊若且唯若原對應平面相鄰且鄰邊頂點著色為紅或藍。
G中頂點的度數：
-V在ABC內度數非0的情況：原三角形頂點著色為紅黃藍、紅藍藍或紅紅藍，其中僅頂點著色為紅黃藍的三角形構造G後形成的頂點度數為奇數。
度數非0的三種情況
-V在ABC內（非v）的點在其餘情況下度數均為0。
