dn）称为图G的度序列．利用度序列解题是一种重要方法．
29.1.13*** 有一个团体会议，有100人参加．其中任意四个人都至少有一个人认识三人．问：该团体中认识其他所有人的成员最少有多少？
解析 先把问题翻译成图论语言．把该团体的成员视为顶点．对于任意两个顶点u、v所代表的成员，当且仅当彼此认识，则在u、v之间联一条边（即相邻）．得到一个含100个顶点的简单图G．已知条件是，图G中任意四个顶点中都至少有一顶点和其他三个顶点相邻．要求图G中度为99的顶点个数的最小值m．
当图G是完全图时，每个顶点的度都是99，所以有100个度为99的顶点．
当图G是非完全图时，图G中必有两个不相邻的顶点u和v．显然d?u?≤98，d?v?≤98．因此图G中度为99的点的个数l≤98．
如果G中除u和v外另有两个顶点x、y不相邻，则u、v、x和y中不存在和其他三个顶点都相邻的顶点，与题意矛盾．因此G中除u、v外任意两个顶点相邻．这说明对G中除u、v外的任意点x，均有d?x?≥97．
如果G中除u、v外的任何x都和u、v相邻，则d?x??99．此时G中度为99的顶点个数为98． 设G中除u、v外有个顶点x和u、v不都相邻，则有G的性质知，G中除u、v、x外的任意顶点y和
u、v、x都相邻．因此d?u?≤98，d?v?≤98，d?x?≤98，d?y?＝99．所以G中度为99的顶点个数为
97．
这表明含100个顶点的简单图G中，如果任意四个顶点中必有一个顶点和其他三个顶点都相邻，那么G中至少有97个度为99的顶点．
回到原问题，即得：该团体中认识其他所有人的成员最少是97个．
评注 本题中的成员数100改为任意的n，其他条件不变，则结论为该团体至少有n?3人认识其他所有人．
29.1.14*** 毕业舞会有男女学生各n人参加，n?2．每个男生都和一些但不是全部的女生跳过舞，每个女生也都和一些但非全部的男生跳过舞．证明：总有两名男生B1、B2和两名女生G1、G2，使得B1和G1，B2和G2跳过舞，但B1和G2，B2和G1都未跳过舞．
解析 用顶点表示参加舞会的学生，男生的全体用X来表示，女生的全体用Y来表示．对任意的x、y，当且仅当所表示的男生和女生跳过舞时令x、y相邻．X的顶点之间以及Y的顶点之间都不相邻． 已知对任意的x、y，都有0?d?x??n，0?d?y??n，要证明图G中含有两条没有公共端点的边．
设x1是X中度最大的顶点，在与x1不相邻的Y的顶点中任选y2．由于y2和x1不相邻，且0?d?y??n，所以y2和X中某个x2相邻．如果x2和所有与x1相邻的顶点相邻，则d?x2?≥d?x1??1，与x1是X中度最大的顶点矛盾．因此，必有y1是x1的顶点但和x2不相邻．于是边x1y1、x2y2没有公共端点． 评注 本题解法有一定典型性，抓住图G中度最大的顶点来解决问题．当然，有时也可以从图G中度最小的顶点入手．
29.1.15*** 设A1，A2，A3，…，A6是平面上的6点，其中任3点不共线．如果这些点之间任意连结了13条线段，求证：必存在4点，它们每两点之间都有线段连结．
解折 将已连结的13条线段全染成红色，还未连上的两条用蓝线连上（因为所有两点连一线段时应该共有15条）．于是必有一个同色三角形，现在的蓝色线只有两条，所以同色三角形必为红色的．不妨设△A1A2A3是红色的．
A1A6A3A5A4A2
从A4、A5、A6引向△A1A2A3顶点各有3条，这9条线段中最多只有2条蓝色，起码有7条是红色的，因此，或者是A4，或者是A5，或者是A6，引向△A1A2A3顶点的线段全是红色．比如说，A4A1、A4A2、A4A3全是红色，那么4点A1、A2、A3、A4的每2点连线全是红色的，命题得证．
29.1.16** 在某城有若干栋（>2）独家住宅，其中每栋住宅住有1人．在一个好天气，每个人都将自己的家搬迁了一次．搬迁后每家仍住1人，只是大家都调换了住宅．证明：在搬迁之后，可将这些住宅分别漆上蓝色、绿色和红色，使得对于每个主人来说，他的新居和旧居颜色不一样．
解析 将住宅一一编号，使得第一座住宅搬出来的人住进第二座住宅，第二座住宅出来的人住进第三座住宅……于是一定存在一个自，使得第矗座住宅搬出的人住进第1座住宅．这是个人形成一个“圈”．如果志为偶数，显然只需要2种颜色，如果＆是奇数，3种颜色足够了．然后再考虑其他人，最后形成一个个互相独立的“圈”（当然也可能只有一个），每个圈独自处理即可．
29.1.17*** 某俱乐部共有99名成员，每一个成员都声称只愿意和自己认识的人一起打桥牌．已知每个成员都至少认识67名成员．证明一定有4名成员，他们可以在一起打桥牌．
解析 作一个图G：用99个点表示99名成员，如果两名成员相互认识，就在相应的两个顶点之间连一条边．已知条件是：对任意顶点v，d?v?≥67．欲证G中含有一个4阶完全图K4．
在G中任取一个顶点u，由于d?u?≥67，所以存在顶点v，使得与v相邻且与u不相邻的顶点至多为（99－1－67＝）31个．同样，与v不相邻且与u相邻的顶点也至多31个．于是图G中至少有（99－31－31－2＝）35个顶点和u、v均相邻．如图所示，设顶点x和顶点u、v均相邻．由于d?x?≥67，并且G中至多只有（3l+31+2＝）64个不同时和u、v均相邻的顶点，因此顶点x至少还和一个与u、v均相邻的顶点y相邻．从而u、v、x、y是4个两两相邻的顶点．于是命题得证．
uv…≤31……≥35…≤31
评注l 若将题中的67人改为66人，则不一定能找出4个互相认识的人来．反例如图所示．将顶点集V分成三个子集{v1，v2，…，v33}，{v34，v35，…，v66}，{v67，v68，…，v99）．同一个子集中任意
两顶点均不相邻，不同子集中的任意两点均相邻．显然每个顶点的度都是66，任意4点中，至少有2点属于同一子集，从而它们不相邻．也就是说图中不存在两两相邻的4顶点．
评注2 本题可推广为：
?2n?俱乐部有n（n≥4）人，其中每人都至少认识其中的???1个人，则在这n个人中必定可以找到4个
?3?人，他们是两两认识的．
29.1.18*** 已知五个城市两两相连所得的10条道路中，至少有一个交叉路口，如图（a）．又已知三个村庄和三个城市相连所需的9条道路中，至少有一个交叉路口，如图（b）．利用上述结论，问：用15条道路把六个城市两两相连，至少会产生多少个交叉路口？