离散数学期末考试要考握手定理，复习一下。
定理1
无向图 G = < V , E > G=<V,E> G=<V,E> 是 ( p , q ) (p,q) (p,q)图( ∣ V ∣ = p , ∣ E ∣ = q |V|=p,|E|=q ∣V∣=p,∣E∣=q)，则 ∑ v ∈ V d G ( v ) = 2 q \sum_{v\in{V}}d_{G}(v)=2q ∑v∈VdG(v)=2q.
证明很简单，一条边会产生两个度，进行q次除边操作，剩下p个零图时，可计算得总度数是边数的两倍。
定义1
度为奇数的结点是奇结点，度为偶数的结点是偶结点。
引理1
任何图都有偶数个奇结点。
例1
一次集会中，相互认识的人会彼此握手，试证明与奇数个人握手的人数是偶数。
证明：
每个人看成是一个结点，两个人之间如果握手则存在一条边，否则无边。则可以对问题建立图模型，由引理1，得证。
扩展：自然数集有限子集上与奇数个数互素的数字个数必为偶数。
例2
每个碳氢化合物的分子所含氢原子数必然是偶数。
证明：
H在碳氢化合物中一定是+1价。建立图模型：每个原子是一个结点，价数决定了某原子与其他原子之间的化学键数，看作是边数（度数）。则由引理1，问题得证。
例3
搬砖问题。
n个码农搬k块砖，其中 k % 2 = = 0 k\%2==0 k%2==0.每人自愿搬一定数目的砖，但是最终要搬完所有的砖（抱一个大腿就可以摸鱼了 ).求证：搬奇数块砖的码农必有偶数个。
证明：
n 个 码 农 为 v 1 , v 2 , . . . . . . , v n , 记 v 0 是 那 k 块 砖 。 n个码农为v_1,v_2,......,v_n,记v_0是那k块砖。 n个码农为v1,v2,......,vn,记v0是那k块砖。
v i 搬 了 m 块 砖 ， 则 在 v 0 与 v i 之 间 连 接 m 条 边 。 v_i搬了m块砖，则在v_0与v_i之间连接m条边。 vi搬了m块砖，则在v0与vi之间连接m条边。
已知 d e g ( v 0 ) = k deg(v_0)=k deg(v0)=k是偶数，则根据定理1, ∑ v i d e g ( v i ) + k = 2 × ∑ v i m i \sum_{v_i}{deg(v_i)}+k=2\times{\sum_{v_i}{m_i}} ∑videg(vi)+k=2×∑vimi
按照度数奇偶划分码农为奇偶码农，显然奇码农应该有偶数个。因为度数之和应该为偶数，而奇结点的度数已经是奇数了，那么奇结点的个数必然是偶数。得证。
例4（原题是清华大学的运筹学教材中，《图论》这一章习题的第2题）整理自某帖子[1]
已知9个人中v1和两人握过手，v2,v3各和4个人握过手，v4,v5,v6,v7各和5个人握过手，v8,v9各和6个人握过手，证明：这9个人中一定可以找出3个人互相握过手。
证明：
即证，这个图中一定有子图是 K 3 K_3 K3(三角形).
根据题目条件，可以计算图的边数为 1 × 2 + 2 × 4 + 4 × 5 + 2 × 6 2 = 21 \frac{1\times2+2\times{4}+4\times{5}+2\times{6}}{2}=21 21×2+2×4+4×5+2×6=21
而 K 9 K_9 K9应该有36条边。 v 9 v_9 v9只与六个人握手，除去自己，最多会与8个人握手，因此，在 K 9 K_9 K9中减去与 v 9 v_9 v9关联的两条边。则总边数剩下34条。不妨记 v i , i = 1 , 2 , . . . , 6 v_i,i=1,2,...,6 vi,i=1,2,...,6与 v 9 v_9 v9握手。
关注 v 9 , v 1 , v 2 , . . . , v 6 v_9,v_1,v_2,...,v_6 v9,v1,v2,...,v6.假设他们中不存在 K 3 K_3 K3子图。而 v 9 v_9 v9与 v i v_i vi中已经存在一条边，则 v i v_i vi之间必然不会有边，否则会构成 K 3 K_3 K3。则需要再减去 C 6 2 = 15 C_6^2=15 C62=15条边，剩下19条边，19<21,与题目条件相互矛盾，因此 v 9 , v 1 , v 2 , . . . , v 6 v_9,v_1,v_2,...,v_6 v9,v1,v2,...,v6之间存在 K 3 K_3 K3子图，即这9个人中一定可以找出3个人互相握过手。得证。
P.S. 可以用图兰定理证明此问题。
[1][https://bbs.csdn.net/topics/320090524?utm_medium=distribute.pc_relevant.none-task-discussion_topic-BlogCommendFromBaidu-6.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-discussion_topic-BlogCommendFromBaidu-6.nonecase]
