每个人都握手的人数之最大值是多少？（“希望杯”邀请赛试题）

解 由题意，把参加聚会的人视为顶点，其集合记作V，对于

，v∈V，如

果u和v所表示的两个人握了手，则令u和v相邻，得到n阶简单图记作G.则图G中至少有一个顶点u，使得

.这表明，图G不是完全图.

要求的是，聚会中和其他所有的人都握手的人数的最大值，即求图G中度为n-1的顶点个数之最大值.于是即求所有n阶非完全的简单图G中度为n-1的顶点个数之最大值m.

由于图G是非完全图，所以至少有两个顶点u和v是不相邻的，因此d(u)≤n-2，d(v)≤n-2.这表明，m≤n-2.

取一个n-2阶完全图Kn-2，另取两个顶点u和v.令Kn-2中每个顶点都和u与v相邻，而u与v不相邻，得到的图记作Kn-2+u+v.很明显，图Kn-2+u+v不是完全图，而且d(u)=d(v)=n-2，并且对除u，v外任意的顶点x均有d（x）=n-1.这表明m=n-2.即聚会中和每个人都握手的人数之最大值是n-2.

例2 有一个团体，由1982个人组成，其中任意四个人中都至少有一个人认识其他三个人.问该团体中认识其他所有人的成员最少有多少？（上海市竞赛题）

解 把该团体的成员视为顶点，其集合记作V.对于u，v∈V，如果u，v所表示的两名成员彼此认识，则令u和v相邻，否则令u和v不相邻，得到的是一个1982阶简单图G.由已知条件可知，如果1982阶简单图G的任意四个顶点中都至少有一个顶点和其他三个顶点相邻.求图G中至少有多少个度为1981的顶点？

当图G为完全图时，图G的每个顶点的度都是1981.所以有1982个度为1981的顶点.

当图G为非完全图时，图G中必有两个不相邻的顶点u和v，显然有d（u）≤1980，d（v）≤1980.因此，图G中度为1981的顶点的个数≤1980.如果图G中除u和v外还有两个顶点x和y不相邻，则u，v，x和y中不存在和其他三个顶点都相邻的顶点，与图G所具有的性质矛盾.因此图G中除u和v外任意两个顶点都相邻.这说明，对G中除u和v外的任意顶点x，都有d（x）≥1979.如果G中除u和v外的任意顶点x都和u与v相邻，则d（x）=1981.此时，G中度为1981的顶点个数为1980.设G中除u和v外有个顶点x和u与v不都相邻，则

4

有题意，G中除u，v和x之外的任意顶点y和u、v与x都相邻.因此，（u）d≤1980，d（v）≤1980，d（x）≤1980，且d（y）=1981.所以G中度为1981的顶点个数为1879,.这表明，如果1982阶简单图G中任意四个顶点中必有一个顶点和其他三个顶点都相邻，则G中至少有1979个度为1981的顶点.

所以，该团体中认识其他所有人的成员最少是1979.

例3 有7为男生与7为女生参加一次舞会，会后统计出各人的跳舞次数为（按从小到大的顺序）：

3，3，3，3，3，4，6，6，6，6，6，6，6，6 （1） 证明其中必有错误.（北京市竞赛题）

证明 用点表示人，如果两个人跳过一次舞，就在相应的两个点之间连一条线.跳舞次数的和就是图中各点的度的和，而（1）中有5个奇数，总和为奇数，这与定理1矛盾！

例4 在例3 中，如果统计的跳舞次数为3，3，3，3，3，5，6， 6，6，6，6，6，6，6，其中是否有错？这里约定男生不与男生跳舞，女生也不与女生跳舞.（北京市竞赛题）

解 我们用黑点表示男生，红点表示女生.在跳过舞的两个人之间用边相连（跳几次就连几次）.根据约定，黑点之间互不相连，红点之间也互不相连.所得的图为二部图，显然

所有黑点的度之和=所有红点的度之和=图中的边数 （2） 但题中给出的14个数中仅有一个数5不被3整除，这样（2）的一边被3整除；另一边恰有一个数不被3整除，从而不被3整除.矛盾！

例5晚会上大家握手言欢，试证握过奇次手的人数是偶数.（全国初中数学竞赛试题）

证 构作一图，以参加晚会的人为顶，仅当二人握手之时，在相应的二项间加一条边.于是没人握手的次数即为所造的图的相应顶之次数.由定理1的推论，奇次顶的个数是偶数，所以握过手的人数为偶数.

例6 大于7公斤的整公斤的重量都可以仅有一些3公斤和5公斤的两种砝码来称量.（《学校报》公开赛试题）

证 只需证明对任意给定的自然数n，存在二部图G(n)，其中X顶子集有n

5

个顶点，每顶都只有一次，Y顶子集中的项是3次或5次的.

下面用数学归纳法证明之：

当n=8时，结论显然成立，如图（4）

x1 x2 x3 x4 x5 x6 x7 x8 y1 y2

假设对于此，在

的

,结论以成立，顶子集中添加一项

图（4）

. 以下证明对，结论仍成立. 为

的

中顶是3

；由归纳法假设，在

次或5次的，分以下两种情形讨论：

(i)若

中皆三次顶，去

，

，,将其重合成一个顶

,再于

与

之间连一条边，最后把劈开成两个5次顶，则得满足要求的

(ii)若Y中有5次顶，设d(yi)?5，在yi与xk?1之间连一边，再把yi劈开成两个3次顶，则得满足要求的二分图G?k?1?.证毕.

2.2欧拉回路和欧拉迹在数学竞赛中的应用

在上节已经提到，度的概念和欧拉定理是著名数学家欧拉为解决所谓哥尼斯堡七桥问题而提出的.古城哥尼斯堡位于普瑞格尔河的两岸及河中的两个岛上，城市的各个部分由七座桥连接.十八世纪，哥尼斯堡属于东普鲁士（纤维苏联的加里宁格勒）.那时候，哥尼斯堡市民生活富足.每到星期天，市民们喜欢四处散布.于是便产生了这样的问题：是否可以设计一种方案，使得人们从家里出发，经过每座桥恰好一次，最后回到家里.尽管许多人试图解决这个问题，但是谁也

6

没有答案.

哥尼斯堡七桥问题引起了欧拉的兴趣.他从人们的失败中敏锐地领悟到，也许那样的方案根本就不存在.1736年，年方二十九岁的欧拉终于解决了这个问题，并在彼得堡科学院报告了自己的结果.欧拉的文章不仅仅是解决了一个难题，而且标志着一个新的数学分支——图论的创立.这一部分将介绍欧拉的研究结果.为此，我先来介绍一些基本的术语.

2.2.1 通路、迹、道路、闭通路、圈和连通图的基本概念

x1 e1 x2 e8 e2 x3 e5 e6 e7 e3 x5

e4 图（5）

x4

设G是一个图，x0，x1，···，xk是图G的某些顶点.如果图G含有边e1=x0x1，e2=x1x2，···，ek=xk-1xk，则由x0，x1，···，xk和e1，e2，···ek组成的点边交错序列（x0，e1，x1，e2，x2，···，xk-1，ek，xk）叫做图G的一条长为k的通路，记作x0x1x2···xk.如果一条通路中所有的边都不同，则称它是一条迹，如图（5），x1e1x2e8x2x4就是一条迹.如果通路中所有的顶点都不同，则称它是一条道路，则图（5）中x1e1x2x4x5是一条道路，始点和终点重合的通路叫做闭通路，则图（5）中x1e1x2e8x2x4x5e5x1是一条闭通路，如果一条闭通路除始点和终点相重合外，其他顶点都不相同，则称它为圈，则图（5）中x1e1x2x4x5e5x1是圈.

设G是一个图，如果图G是一阶图，或者图G的阶大于1，并且对图G中任意两个顶点u和v，总有一条以u为始点且以v为终点的通路，则图G叫做连通图，否则图G叫做不连通的.图（5）就是一个不连通的

根据直观感受，可以想到，对给定的图G，它的顶点的度越大，它的边数也

7