握手定理

給定無向圖𝐺 =(𝑉,𝐸)，有∑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=偶數)=偶度頂點的度數之和(偶數)+奇度點的頂點度數之和，所以

偶度頂點的頂點度數之和是一個偶數，而奇數個奇數為奇數，故奇數點的個數必為偶數。

握手定理也稱為圖論的基本定理，圖中頂點的度數是圖論中最為基本的概念之一。

Δ是平面上一個三角形。f:Δ→Δ連續：

布勞威爾不動點定理：每個連續函數f:Δ→Δ有一個不動點。

HEX game：兩個玩家，分別用紅色和藍色對平面上一個內部被分割為若干三角形的正方形着色。玩家從一個正方形頂點開始着色（兩個玩家開始的頂點不在對角線上），每次着色一個頂點，下一次着色的頂點必須與上一次着色的頂點相鄰，先着色到對角線上另一個頂點的玩家獲勝。

對頂點v用數字標記：

若此命題不成立，則頂點c,d都被標記為3。由Sperner引理知，一定有一個包含三個不同標記1、2、3的三角形。如果c,d都被標記為3，則這個三角形如圖所示。但這顯然違反了標記規則，故c被標記為1和d被標記為2至少有一個成立。所以RED與BLUE之一會獲勝。 ^[1] 

無向圖中，度數為奇數的點一定是有偶數多個。

定理(Smith)：對3-正則圖，包含圖上任意邊𝑒的哈密頓迴路必有偶數條。

證明：(Thomason 1978)

圖𝐺是3-正則圖，𝑒 = {𝑣1, 𝑣2}是一條固定的邊，不失一般性，假設原圖中有含有𝑒的哈密頓迴路。

構造圖𝐺′= (𝑉′, 𝐸)

· 𝑉′中的每一點，代表一條從𝑣1開始，以𝑒為第一條邊的哈密頓路徑（由前提假設知𝑉′非空）

構造𝐸'：

𝑣𝑝 ∈ 𝑉' 代表哈密頓路徑P

𝑣𝑛在𝐺中度數為3，故必存在

滿足𝑣𝑘, 𝑣𝑛 ∈𝐸(𝐺)；

𝑃′= 𝑣1 𝑣2 … 𝑣𝑘 𝑣𝑛 𝑣(𝑛−1) … 𝑣(𝑘+1)是哈密頓路徑。𝑣𝑝' ∈ 𝑉′；

{𝑣𝑝, 𝑣𝑝'} ∈ 𝐸'

𝐸'中任意𝑣𝑝的度數至多為2：

𝑑𝑒g(𝑣𝑝) = 1當且僅當原始用到的哈密頓路徑實際上是圖𝐺𝐺中一個哈密頓迴路。

已知平面上的一個三角形ABC，它被任意劃分為若干小的不重疊的三角形。用紅、黃、藍依次對A、B、C三個頂點着色。對其餘頂點：BC邊上的點用黃或藍着色；AB上的點用紅或黃着色；AC邊上的點用紅或藍着色。其他內部頂點任意着色。

引理的一般形式：

Sperner's lemma(Sperner,1928):對任意n維單形體（n-simpex）進行分割並用n+1種顏色去着色，則任何合適的單形體分割着色方案下，都必有一個包含所有不同顏色的單元。 ^[1]