握手定理：有n个人握手，每人握手x次，握手总次数为S= nx/2。

给定无向图𝐺 =(𝑉,𝐸)，有∑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=偶数)=偶度顶点的度数之和(偶数)+奇度点的顶点度数之和，所以

偶度顶点的顶点度数之和是一个偶数，而奇数个奇数为奇数，故奇数点的个数必为偶数。

握手定理也称为图论的基本定理，图中顶点的度数是图论中最为基本的概念之一。

（1）不动点（Fix point）

Δ是平面上一个三角形。f:Δ→Δ连续：

布劳威尔不动点定理：每个连续函数f:Δ→Δ有一个不动点。

（2）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之一会获胜。

无向图中，度数为奇数的点一定是有偶数多个。

定理(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引理：必然存在一个三个顶点都不同色的三角形。

证明：构造图G=(V,E)。

V:每个闭合的连续平面（小三角形）抽象为一个点，外面的开放平面也抽象为一个点，取名为v。

E:两个顶点之间有一条边当且仅当原对应平面相邻且邻边顶点着色为红或蓝。

G中顶点的度数：

-V在ABC内度数非0的情况：原三角形顶点着色为红黄蓝、红蓝蓝或红红蓝，其中仅顶点着色为红黄蓝的三角形构造G后形成的顶点度数为奇数。

-V在ABC内（非v）的点在其余情况下度数均为0。

-V在ABC外的点（点v）的度数：就是AC边上颜色的改变次数，易证其必为奇数（只能使用红、蓝，由红经过若干次改变为蓝）。

根据握手定理，G中必还有度数为奇的点，即ABC内必存在顶点着色为红黄蓝的三角形，得证。

引理的一般形式：

Sperner's lemma(Sperner,1928):对任意n维单形体（n-simpex）进行分割并用n+1种颜色去着色，则任何合适的单形体分割着色方案下，都必有一个包含所有不同颜色的单元。