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

顶点的度数与握手定理

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

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=偶数)=偶度顶点的度数之和(偶数)+奇度点的顶点度数之和，所以

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

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