握手定理：有n個人握手，握手次數的總和S，必有S≤

2(n+1)。

頂點的度數與握手定理

--------------------------------------------------------------------------------

1．頂點的度數

定義14.4

設G=<V，E>為一無向圖，v∈V，稱v作為邊的端點次數之和為v的度數，簡稱為度，記做

dG(v)，在不發生混淆時，簡記為d(v).設D=<V，E>為有向圖，v∈V，稱v作為邊的始點次數之和為v的出度，記做(v)，簡記作d+(v).稱v作為邊的終點次數之和為v的入度，記做(v)，簡記作d-(v)，稱d+(v)+d-(v)為v的度數，記做d(v).

--------------------------------------------------------------------------------

2．握手定理

定理14.1(握手定理)

設G=<V,E>為任意無向圖，V={v1,v2,…,vn}，|E|=m，則

所有頂點的度數和=2m

證

G中每條邊(包括環)均有兩個端點，所以在計算G中各頂點度數之和時，每條邊均提供2度，當然，m條邊，共提供2m度。

定理14.2(握手定理)

設D=<V,E>為任意有向圖，V={v1,v2,…,vn}，|E|=m，則

所有頂點的度數和=2m，且出度=入度=m.

本定理的證明類似於定理14.1

握手定理的推論

任何圖(無向的或有向的)中，奇度頂點的個數是偶數。

證

:

所有頂點的度數和(2m=偶數)=偶度頂點的度數之和(偶數)+奇度點的頂點度數之和，所以

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

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