握手定理

握手定理 握手定理：有n个人握手，握手次数的总和S，必有S≤ 2(n+1)。
顶点的度数与握手定理
--------------------------------------------------------------------------------
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
握手定理的推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数。
证 设G=为任意一图，令
V1={v|v∈V∧d(v)为奇数}
V2={v|v∈V∧d(v)为偶数}
则V1∪V2=V，V1∩V2=，由握手定理可知
2m==+
由于2m，均为偶数，所以为偶数，但因V1中顶点数为奇数，所以|V1|必为偶数。
握手定理也称为图论的基本定理，图中顶点的度数是图论中最为基本的概念之一。
握手问题

一位先生说：“前此日子，我同我太太一起参加了一个宴会，酒席上还有另外四对夫妻。见面时，大家相互问候，亲切握手。当然，没有人会去同自己的太太握手，自己也不会同自己握手，与某一个人握过手之后，也不可能再同他或她进行第二次握手。
“彼此之间的握手全部结束之后，我好奇地询问在座的各位先生和女士，当然也包括我太太在内，每人各握过几次手？
“使我惊奇的是，每个人报出的握手次数竟完全不一样。请问：我太太同别人共握了几次手？”
为了使这个问题的叙述更为严密，还需作如下说明：
(1)甲与乙握手，在计算握手次数时，甲算一次，乙也算一次。
(2)握手并不要求一个都不漏，可握而未握的情况也是有的，例如，行注目礼，双手合掌，拍拍肩膀，对方正在与别人握手不便越位等等，这当然不算不礼貌。不过，这样一来就大大地增加了问题的复杂性，使问题似乎变得无从求解了。
解决这个问

题，主要是运用逻辑推理。既然宴会上共有10人，任何人都不同自己握手，也不同配偶握手，所以任何一个人握手的次数最多只能等于8。由于这位先生已问过各位宾客，得知他们每人握手的次数都不一样，可见这9个人的握手次数必定是0，1，2，3，4，5，6，7，8。显然握手次数为8的那一位已同除了自己的配偶以外的每个人都握过了手，所以这个人（无法判定这个人是先生或女士）的配偶必定就是那个握手次数为0的人。由于这两个人的关系已被确定，于是就可以请他们退到“圈子”以外。
接着可以推定，握手次数为7的人必定与握手次数为1的人是一对夫妻；握手次数为6的人必定与握手次数为2的是一对夫妻；如此等等。
最后只剩下握手次数为4的人，可以断定，此人肯定是提出问题的那位先生的太太。
解决问题之后，让我们再来回顾这道题目，对称性、递归性、消去法都从这道题中得到了很好的体现，怪不得一些评论家们说：这样的数学题目，真是太“艺术化”了。
此题的发明权，属于当代美国数学科普大师——马丁·加德纳。