1、第67讲 图论问题(一)本节主要内容是：把一个具体问题用图形表示出来，利用图形的直观性可能更有利于问题的解决有关的一些概念：由若干个不同的点及连接其中某些点对的线所组成的图形就称为图图中的点的集合称为图的点集，记为V：Vv1，v2，vn，；图中的线的集合称为图的线集(边的集合)，记为E：Evivj(vi，vjV)故一个图由其点集V和线集E所决定，若用G表示图，则记为GG(V；E)含有n个点的图称为n阶图在一个图中，如果某点v共连了k条线，则说此点的“次数”(或“度数”)为k，记为degvk.如果一个p阶图的每两个顶点间都连且只连了1条线，则称该图为p阶完全图，记为Kp若对每条线确定一个方向(即
2、确定了线的两个端点中一个为“起点”，另一个为“终点”这时，线是点的“有序对”)，则得到“有向图”；对有向图的一个顶点v，degvk，若v是其中n条边的起点，m条边的终点(mnk)，则称v的出次为n，入次为m链：若在一个图G(V；E)中取n+1个顶点 v1、v2、vn+1，每两个相邻的顶点vi、vi+1间连有一条边li,则边l1,l2,ln就称为从v1到vn+1的一条链n称为链的长度A类例题例1 证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着乙认识甲) K6的边染成红蓝两色，求证：其中必有两个三角形，其三边同色分析 以点表示人，连红、蓝两色的线分别表示“认识”与“不认识”，
3、问题转化成图的问题要会把题目的语言转译成图的语言：“三人互相认识”就表示三点间都连红线，“三人互不认识”就表示三点间都连蓝线 考虑每个异色三角形的三个角，其中两个角是异色角，而同色三角形的三个角都是同色角证明 用6个点v1，v2，v6表示这6个人，如果某两人相互认识，则在表示此二人的点间连一条红线，否则连一条蓝线于是问题转化为证明此6点间一定连出了三边均为红色或蓝色的三角形在点v1连出的5条线中，由抽屉原理知，必有某色线连有3条或3条以上不妨设红线连了至少3条设v1与v2、v3、v4连的红线现考虑点v2、v3、v4连线的情况，如果此三点间有任两点连的红线，则出现红色三角形(例如v2v3连红线，
4、则v1v2v3是红色三角形)，如果这三点间都不连红线，则出现蓝色三角形(v2v3v4是蓝色三角形)故证 考虑K6共连了C15条线，共得到C20个三角形设第i个顶点连了ri(0i5)条红线，5ri条蓝线由于ri(5ri)6所以，连出的异色角个数6636个由于每个异色的三角形有2个异色角，所以图中异色三角形个数18，故图中同色三角形个数20182说明 题是早期匈牙利的一个图论竞赛题解这类“实际问题”时，重要的是会用图的语言解释题意，把实际问题改写为图的问题 用异色角来解相关问题是较好的方法例2 由5人组成一个公司，其中任意三人总有2人彼此认识，也总有2人彼此不认识证明：这五人可以围桌而坐，使每人两
5、旁都是他认识的人(1978年保加利亚数学竞赛)证明 用5个点表示这5个人，若两人互相认识，则在表示这2个人的点间连1条线题目的条件即是：任三点间至少连1条线，但不能连3条线首先，每点都至少连了2条线，若点v1只连出1条线，则它至少与某三点(设为v2、v3、v4)未连线，则此3点间都要连线(若v2与v3没有连线，则v1与v2、v3就都没有连线，与已知矛盾)出现了以v2、v3、v4为顶点的三角形，矛盾其次，若某点连出了3条线，则此三点间都不能连线，与已知矛盾故知：每点都恰连2条线它不能连成三角形，也不能连成四边形，否则余下的点无法连线，故只能如图所示，证毕说明 仔细体会上述两例的特点，明白什么时候
6、应该用图来解相关的题：当涉及多个元素的某些相互关系时，就可能用图来解释情景再现1在例1中，把6个人改为5个人，结论是否一定成立？2图G有n个顶点，n+1条边，证明：图G至少有一个顶点的次数3B类例题例3 设竞赛图(每两个点都连了1条线的有向图)中，点Ak的出次与入次分别为wk与ek(k1，2，n)，证明 wwweee分析 根据竞赛图的特点可知： 每点的出次与入次的和都等于n1， 所有点的出次的和与入次的和相等由此可以推出：所有点的出次和与入次和都等于n(n1)这是两个基本的性质在要证的式子中把ek用n1wk代替证明 对于每个点，出次与入次的和都是n1，即wkekn1(k1，2，n)， 所有出次
7、的和与所有入次的和相等，且都等于图中弧的条数：w1w2wne1e2enn(n1)所以 eee(n1w1)2(n1w2)2(n1wn)2n(n1)2www2(w1w2wn)(n1)wwwn(n1)22(n1)(n1) www说明 本题的证明方法与奇偶分析中的例6相似例4 平面上给定7个点，用一些线段连接它们，每三个点中至少有两点相连，问至少要有多少条线段？试给出一个图(1989蒙古数学竞赛)分析 首先找到连线条数的下界(即至少要连出多少条线)，再寻找是否可能达到这个下界，可以分别枚举可能的连线方法，讨论每种方法的连线条数，得到最小的结果解 7个点中共有三点组C=35个每条线段共与其余5点组成5个
8、三角形故线段条数7条如果有一个点没有连线，则其余6点两两都必须连线，要C15条如果有一点只连了一条线，其余5点必须两两连线，连线数C10条 设某点只连了2条线，如点A只连了AB、AC这2条线，则其余4点均未与A连线，于是它们必须两两互连，应连C=6条此时，取B、C两点及其余4点中的任一点，尚不满足条件，故BC应连线，此时连了9条线，所得图形满足题目要求若每点都至少连出3条线，则总度数21，即至少连了+111条线所以，至少连9条线例5 九名数学家在一次国际会议上相遇，发现他们中的任三人中至少有两人能用同一种语言对话，如果每个数学家至多会用三种语言证明：至少有三人可用同一种语言对话(1978年美国
9、数学竞赛)分析 9个人用9个点表示证法1中，多种语言则用多种颜色的线来表示，转译结论“三人可用同一种语言对话”时，应注意：如果从一点向另两点连出了同色的两条线，表示另两人也能用相应的语言对话，从而就出现了同色三角形所以，只要证明从一点一定引出了同色的线即可而在证法2中，改设若二人不能对话就连1条线(即不存在二人都会的语言)此时结论就应转译为“存在三点，两两都没有连线”证法1 用9个点表示这9个人，某二人如能用第r种语言交谈，则在表示此二人的点间连一条线，并涂上第r种颜色，于是，本题即是证明，存在一个同色的三角形首先，若v1与v2、v1与v3间都连了第k种颜色线，则v2与v3间也要连第k种颜色线
10、此时即出现同色的三角形所以只要证明从其中某一点出发的线中必有两条线的颜色相同反设从任一点出发的线中没有同色的线，由于每个人至多会用三种语言即degvi3，于是v1至少与5个点不邻接，设为v2、v6，同样，v2至少与5个点不相邻接，于是v3、v6中至少有一点与v2不相邻接设为v3，于是v1、v2、v3不相邻接与已知“任三人中都至少有两人能用同一种语言对话”矛盾故证证法2 取9个点v1，v2，v9表示9个人，如果某二人不能对话，则在表示此二人的点间连一条线，于是在任何三点间，都有两个点不相邻，即不存在三角形如果有人至少与4个点不连线，由于他最多只能讲三种语言，则他必与其中某两人讲同一种语言于是相应
11、三人可以用同一种语言来对话下面证明存在一点，其度不大于4从而该点至少与4点不相邻如果degv14，则v1即为所求若degv14，则至少degv15，即至少有5个点与之连线，设为v2，v6，由于这些点不能连出三角形，故v2，v6的任何两个之间都不能连线，从而v2与v3，v6均无连线，于是degv24即可证得原题说明 两点间连了1条线，则说这两点相邻本题的两种证明方法从两个方向出发，一种是两人可用同一种语言通话，就在相应两点间连一条边，证法2是反过来，两人不能通话时则连一条边，都能应用图解决问题例6 俱乐部里有14个人想打桥牌，已知过去每个人都与其中的5个人合作过，现在规定4个人中必须任两个人都没
12、有合作过才准许在一起打1局桥牌，这样打了3局就无法再打下去了，如果这时又来了一人，他与原来的14个人都没有合作过，证明：一定可以再打1局分析 打桥牌时，4人分成合作的两对，合作的两人坐在相对的位置打牌于是每局桥牌，都有两对人合作把题目的条件与结论都转述为图的语言，并找出结论的等价命题是：找到三个人互相都没有合作过，即存在3个点互不相邻证明 用14个点表示这14个人，若某两人合作过，则在表示这两人的点间连一条线，于是，题目条件即：其中每个点都已连出了5条线，且在此14个点中，可以找出3组点(每组4个点)，这三组点间，两两未连线，若这3组点之间共连出6条线后，对于任意4点，都至少有两点连了线(14
13、个点间一共连了41条线)，证明此时一定存在3个点，两两都没有连线(从而添入第15个点后，可与此3点合成4点，两两无连线)由于14个点中的每个点原来都与(1415)8个点不相邻在又打3局连出了6条边以后，至多有12个点又连了线，所以至少还有2个点，每个点仍与8个点不相邻设其中一点为v1与v1不相邻的点集为S下面证明：S中必有一点v2至少与7个点不相邻反设不存在这样的点，则此8点中，每个点都至多与6个点不相邻，故此8个点都至少连了(1461)7条边，于是此8点中的每个点又都新连了至少2条边，故又新连出了8228条边(除以2是因为每条边可能在两个点端点处被计算了2次)这与只连了6条边矛盾，所以存在S
14、中的一点v2，至少与7个点不相邻但8+71514，必有一点v3与v1，v2均未连线此三点即为所求链接 v3存在是根据容斥原理：把这14个人的集合记为S，与v1相邻的点集记为A，与v2相邻的点集记为B，则ABS故card(AB)card(S)而 card(AB)card(A)card(B)card(AB)，故 card(A)card(B)card(AB)card(S)，现card(A)card(B)15，card(S)14，于是card(AB)0情景再现ABCD3右面的有向图由4个顶点及一些弧(有向线段)组成，指出各点的出次(引出的弧的条数)与入次(引入的弧的条数)求出上题中所有各点的出次的和与
15、入次的和，它们与弧的条数有什么关系？证明：任一有向图中，出次的和与入次的和相等4在n(n3)个点的竞赛图中，一定有两个点的出次相同吗？5在集合S的元素之间引入关系“” 对于任意两个元素a，bS，要么ab，要么ba，二者有且只有一个成立； 对任意三个元素a，b，c，如果ab，bc，则ca问集合S中最多能有多少个元素？(1972年英国数学竞赛)6证明： 如果竞赛图中各点的出次不等， 那么可将这些点排成一列，排在前面的点有弧到达排在后面的任一点(即排在前面的选手胜排在后面的所有选手) 如果点数n3的竞赛图中有三角形回路，那么，图中必有两点的出次相等C类例题例7 某足球赛有16个城市参加，每市派出2个
16、队，根据比赛规则，每两队之间至多赛一场，同城两队之间不进行比赛赛过一段时间后，发现除A城甲队外，其他各队已赛过的场数各不相同问A城乙队已赛过几场?证明你的结论分析 注意分析“各队赛过场次各不相同”的含义，即能推知比赛场次的取值情况再从比赛场次最多的队开始讨论，与之比赛的队是哪些队？证明 用32个点表示这32个队，如果某两队比赛了一场，则在表示这两个队的点间连一条线否则就不连线由于，这些队比赛场次最多30场，最少0场，共有31种情况，现除A城甲队外还有31个队，这31个队比赛场次互不相同，故这31个队比赛的场次恰好从0到30都有就在表示每个队的点旁注上这队的比赛场次考虑比赛场次为30的队，这个队
17、除自己与同城的队外，与不同城的队都进行了比赛，于是，它只可能与比赛0场的队同城；再考虑比赛29场的队，这个队除与同城队及比赛0场、1场(只赛1场的队已经与比赛30场的队赛过1场，故不再与其它队比赛)的队不比赛外，与其余各队都比赛，故它与比赛1场的队同城；依次类推，知比赛k场的队与比赛30k场的队同城，这样，把各城都配对后，只有比赛15场的队没有与其余的队同城，故比赛15场的队就是A城乙队即A城乙队比赛了15场说明 有些题的已知条件讨论起来头绪纷繁，如果利用图来讨论则可以化繁为简利用点与线的相邻与否来研究这一类题目需要一定的技巧，也需要相当的抽象概括能力与逻辑推理能力请大家多做些练习例8 n(n
18、3)名乒乓球选手单打若干场后，任意两个选手已赛过的对手恰好都不完全相同，试证明：总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同(1987年全国高中数学联赛)分析 本题的求证暗示要用反证法，设去掉任一个选手，都会有两个选手赛过的对手完全相同于是这两人组成一个点对这样就会得到n个点对每个点对连一条线，n个点连出了n条线，就可用图的性质得到圈，使问题得证这是证法1的思路每个选手的对手可以组成集合，研究对手集的性质，用最小数原理来证明，这是证法2的思路证法1 把这些选手编为1至n号，以n个点表示这n个人，各点也相应编为1至n号反设去掉任何一个选手后，都有两个选手的
19、已赛过的对手完全相同于是，如果先去掉1号选手，则有两个选手的已赛过的对手完全相同，设为第i号与第j号，在表示此二人的点间连一条线，并在线上注上“1号”这说明，此二人在去掉1号选手之前必是一人与1号赛过，另一人与1号没有赛过而且不可能在去掉1号后有三人都相同，否则，此三人与1号选手比赛的情况只有两种：赛过或没有赛过，如果去掉1号后，此三人的情况完全相同，则去掉1号之前必有2人赛过的对手完全相同(如果去掉1号后有不止一对选手的已赛过对手完全相同，则只任取其中的一对连线，其余的对则不连线)同样，如果再依次去掉2号、3号，直至n号，每去掉1个选手，都会在某两点之间连1条线这样，就在n个点间连了n条线且
20、这些线上分别注了1至n号，每条线注了1个号码，每个号码只注在1条线上由于在10个点间连了10条线，故图中必存在一圈现从圈上一点i出发，经过点j、k、最后回到点i注意到点i与点j所代表的两个选手中1个是与1号比赛的，另一个是没有与1号比赛的，不妨设i号没有与1号比赛过，j号与1号比赛过而j与k所连线上注的号码不是1，故j与k与1号比赛的情况相同，即k号与1号比赛过，这样沿线走一圈后回到i，就应该得出i号与1号比赛过，矛盾故证证明2 用A、B、表示选手，而用(A)、(B)表示A、B已赛过的对手集合显然，若A(B)，则B(A)设A是对手集中元素最多的的选手若命题不成立，则存在两个选手B、C使去掉A后
21、，B、C的对手集相同，由于(B)(C)，故A必属于(B)与(C)之一不妨设A(B)，于是，B(A)，C(A)且(C)(B)A(在(B)中去掉它的一个元素A后的集合表示为(B)A)同样对于选手C后，存在D、E，使去掉C后，D、E的对手集相同，即去掉C后，(D)(E)，又设C(D)且C(E)，于是D(C)，E(C)由于A(C)，D(C)，故DA：又D(C)，故D(B)，即B(D) (E)C，从而B(E)，C(E)，而去掉A后，B、C的对手集相同，从而EA于是(A) (E) (D)C，即(A)比(D)少一个元素C，这与A是“对手集中元素最多的”矛盾故证说明 证法1是根据如下结论：如果n个点间连了n条
22、线，则必出现“圈”：即从某一点出发，沿边前进，最后还能回到出发点证法2用最小数原理对集合的元素进行讨论，较难理解，可对照图理解相应的结论链接 树与圈若在一个图G=(V；E)中取n+1个顶点 v1、v2、vn+1，每两个相邻的顶点vi、vi+1间连有一条边li,则边l1,l2,ln就称为从v1到vn+1的一条链一个图中的任意两个顶点间如果都有一条链，该图就是连通的一条链的两个端点v1与vn+1重合时，就称为圈没有圈的连通图称为树n阶树可以记为Tn在一个图中，次数为1的顶点称为悬挂点定理1 如果树T的顶点数2，那么，它至少有两个悬挂点从树的任何一个顶点出发，沿某个方向前进，已走过的边不重复走，由于
23、树是无圈的，故每个顶点至多走过1次，如果，经过的一个顶点不是悬挂点，则还可以前进到下一个顶点，由于树的顶点只有有限个，故前进到某个顶点(如果图中共有n个顶点，则至多前进n1步)后就无法再继续前进，即到达一个次数为1的顶点此顶点即为一个悬挂点再从此悬挂点出发，沿链走一次(第一步是按刚才的反方向前进)，则又可以到达一个悬挂点此悬挂点与刚才第一个悬挂点不同即图中至少有两个悬挂点定理2一个n阶的连通图是1个树，当且仅当它有n1条边先证明：如果树T的顶点数为n，则其边数为n1证明 对于n1或2，定理显然成立设定理对于k个顶点时成立，即若一个树有k个顶点，则其边有k1条对于k+1个顶点的树，只要去掉一个悬
24、挂点及与之相邻的一条边，就成为有k个顶点的情形，此时的树有k个顶点与k1条边，此时再把去掉的1个顶点及1条边添入，就成为k+1个顶点，k条边的树故证再证明：如果图G是连通的，且有n个顶点与n1条边，则G是一个树取G的生成树T，则此生成树有n个顶点，因是树，故有n1条边但TG，故TG故证定理3 树T具有以下性质： 在T中去掉任一边后，所得的图是不连通的； 在T中添上1条边后，所得的图有圈； T中的任两个顶点v1与v2间有且仅有1条链证明 设树T有n个顶点与n1条边，在T中去掉1条边后得到图G，如果G仍连通，则G仍是一个树(因无圈且连通)应有n1条边，矛盾 如添上1边后仍无圈，则仍为树，有n个顶点
25、与n条边，矛盾 由T连通，故v1与v2间必有链，若v1与v2间有不完全相同的两条链，则此图中有圈，即不是树矛盾，故v1与v2间有且仅有1条链 情景再现7某个团体有1982个人，其中任意4人都至少有一人认识其他三个人，认识其他所有人的人数最少是多少？(1982年美国数学竞赛)8在一所房子里有10个人，其中任意3人中至少有2人互相认识，证明：其中有4人，他们任意2人都互相认识(1980英国数学竞赛)如果把中的数10改为9，结论仍成立否？(1977年波兰数学竞赛)习题131如果每个点的出次都是2，那么，一个点经过两条弧就可以到达的点至多有几个？经过一条弧或两条弧可以到达的点至多有几个？2在竞赛图中必
26、有一个点，从它到其它的顶点，只需经过一条弧或两条弧3一个有n个点的竞赛图，各点的出次为w1w2wn如果w1n1，w2n2，wk1n(k1)，但wknk(1kn)证明：wknk4 如果在点数n3的竞赛图中，有两个点的出次相等证明，图中必有三角形回路(即有三个选手A、B、C，其中A胜B，B胜C，C又胜A) 在一个n人参加的循环赛中，每两人比赛一场，如果没有平局，参赛者赢的场数分别是w1，w2，wn求证：出现三个参赛者A，B，C，满足A胜B，B胜C，C胜A的充分必要条件是www5亚洲区足球小组赛，每组有4个队，进行循环赛，每两个队赛一场，胜者得3分，负者得0分，平局各得1分，赛完后，得分最高的前两名
27、出线如果几个队得分相同，那么便抽签决定这些队的名次，问一个队至少要得多少分，才能保证一定出线？6条件同上题，问一个队如果出了线，它至少得了多少分？7在88棋盘上填入164的所有整数，每格一数，每数只填一次， 证明：总可以找到两个相邻的方格（具有公共边的两个方格叫相邻）， 在此两个方格中填入的数的差不小于5？8平面上有n条直线，把平面分成若干个区域.证明:用两色就足以使相邻的区域都涂上不同的颜色.9在某个国家，任意两个城市之间用下列交通工具之一进行联络：汽车，火车和飞机已知没有一个城市拥有这三种交通工具，并且不存在这样三个城市，其中任意两个在联络时都用同一种交通工具而且这个国家用了这三种工具这个
28、国家最多有多少个城市？(1981年保加利亚，美国数学竞赛)10一个大三角形的三个顶点分别涂红、黑、兰三色，在三角形内部取若干点也任意涂红、黑、兰三色之一，这些点间连有一 些线段，把大三角形分成若干互相没有重叠部分的一些小三角形.求证:不论怎样涂，都有一个小三角形，其三个顶点涂的颜色全不同.11证明：在2色K6中一定存在两个同色三角形（即同色K3）12某个国家有21个城市，由若干个航空公司担负着这些城市之间的空运任务每家公司都在5个城市之间设有直达航线(无需着陆，且两城市间允许有几家航空公司的航线)，而每两个城市之间都至少有一条直达航线问至少应有多少家航空公司？(1988年前苏联数学竞赛)本节“
29、情景再现”解答：1解 如图的5个点即不存在同色三角形，故例2中把6个人改为5个人后，结论可能不再成立2证明 计算每个顶点引出的边的条数(次数)，如果每个顶点的次数都2，则统计得到的边数2n，但每条边都被统计过2次，故应统计得到边数=2(n+1)矛盾故至少有一个顶点，其次数33解 点A：出次3，入次1；点B：出次1，入次1；点C：出次0，入次2；点D：出次1，入次1RJ 出次的和=3+1+0+1=5；入次的和=1+1+2+1=5出次的和=入次的和证明 由于每条弧起点所是出次的点，终点都是入次的点，故出次和与入次和相等，都等于弧的条数ABCD4解 不一定，例如右面的一个图中，就没有两个点的出次相同
30、A、B、C、D四点的出次依次为3，2，1，0一般的n个点的竞赛图中，可以出现n个点的出次分别为n1，n2，n3，2，1，0这n个值，于是不一定有两个点的出次相同5解 S中有3个元素是可以的，abca满足要求若S至少有4个元素，取其中4点，由， S中每两点间都要连出1条有向线段，4点间连出6条有向线段每条有向线段都记一个出次，共有6个出次因此至少有一个点至少有2个出次设ab，ac，则无论bc或是cb均引出矛盾即S的元素个数3故S最多有3个元素 6证明 设共有n个点，由于各点出次互不相等，故这n个点的出次取得0，1，2，n1这n1个值中的每个值把出次为0的点排在最后，其余各点均到达此点出次为1的点
31、必到达此点，由于出次为1的点只到达1个点，故出次为1的点只到达出次为0的点，把出次为1的点排在倒数第二位；再考虑出次为2的点，由于此点只到达2个点，故它只到达已排的两个点而不能到达其余的点，把出次为2的点排在倒数第3位；，依此类推，把出次为k的点排在倒数第k+1位，直到出次为n1的点排在第1位这就得到满足题目要求的排法 反设图中所有各点的出次均互不相等，则由上题，可把这些点排成一列，使前面的点到达后面的点而后面的点不能到达前面的点，于是该图中没有回路，与已知此图有回路矛盾故必有两点出次相等7解 先证明：任意4人中都有1人与其余n1人认识用n个点表示这n个人，若两个人认识，则在表示这两个人的点间
32、连一条实线，否则连一条虚线设任取4人v1、v2、v3、v4，其中v1与v2、v3、v4都认识，但此四人中无人与n1人都认识即每个点都有与之不相邻的点设与v1、v2、v3、v4不相邻的点分别为v1、v2、v3、v4，显然v1v2，v2v1，若v1v2，则四点v1、v2、v1、v2不满足题意于是v1=v2，同理v1=v3，于是得v1=v2=v3，此时v1、v2、v3、v1这四点仍不满足已知条件故证又证 设图G中度数小于n1的点为v1、v2、vk，记F=v1、v2、vk，用实线表示相邻(认识)，用虚线表示不相邻若k4，则命题正确(因为图中找不到4个人，他们中任1人都没有与其余n1人认识)若k4，由于
33、vk+1、vk+2、vn的度数都=n1，故与v1不相邻的点都在F中，设为v2，此时若还能找到v3、v4F，且v3与v4不相邻则此四人不满足题目要求(图7)若在F中除v1、v2外无不相邻的人，则v3、vk均至少与v1、v2中某一人不相邻则如图、，亦与已知矛盾故k4不可能故证再考虑本题：把1982个人中的任意4人组成一组，该组中必有1人认识其余所有的人去掉这个人，在余下的人中再任取4人，又成一组，又可找出一个认识其余所有人的人；，这样一直做下去直到余下3人为止，此3人可能与其余的人不全认识故至少有1979人认识其余所有的人8解 用10个点表示这10个人，如果某2人互相认识，则在表示这两人的点间连1
34、条线即任3点都至少连了1条线，要求证明存在一个K4设不存在K4，即任意4点中总有2点没有连线， 设某一点A与4点都没有连线，则由假设此4点中有2点未连线，则此2点与A共3点均未连线，与题设矛盾故A至多与3点未连线，即至少与6点连了线 设A与A1、A2、，A6连线，则A1，A6中任意3点必有2点未连线，否则存在K4， 设A1与Bi、Bj、Bk都未连线，则Bi、Bj、Bk间若有两点未连线，则出现3点，都未连线，与已知矛盾故此三点间都连了线，于是此三点与A成为K4 由知A1，A6中任一点至多与其余5点中的2点未连线即与其余5点中至少3点连了线设A1与A2、A3、A4连了线此时A2、A3、A4间至少连
35、了1条线，设A2A3连了线，则A、A1、A2、A3成为K4由上证可知，不存在K4的假设不成立 若有某点连出6条线，则如上证若每点连线数6，当每点连线数都=5时此时9个点连线统计为45，为奇数不可能若有某点连线数5，即该点至少与4点未连线，则如上，矛盾从而必有点连线数6的点“习题67”解答：ABCDEFG1解 一个点经过两条弧就能到达的点至多有4个经过一条弧或两条弧就能到达的点至多有6个如图，每个点的出次都是2，点A经过1条弧能到达B、C，点B、C分别经过1条弧可以到达D、E、F、G，故点A经过1条或2条弧可以到达至多6个点其中如果有些点重合，则点A可以到达的点就少于6个2证明 取出次最多的点为
36、A，则A的出次(n1)他可以经一条线到达的点为B1，B2，Bm，m(n1)对于A不能到达的点C，若B1，B2，Bm中没有点到达C，则不能到达C的点至少有m+1个，即C的出次比A多，与A为出次最多的点矛盾故所有A不能到达的点，都可经2条线到达故证3证明 k1时，若w1n1，则w1n1设w1n1，即w1到达所有其余的点把出次为w1的点去掉，这对余下的点的出次都不受影响此时就得到一个只有n1个点的竞赛图若w2n2，则w2n2设w1n1，w2n2，同上两次去掉出次为w1，w2的点，则得到一个有n2个点的竞赛图其中每个点的出次n3于是若w3n3，就有w3n3依此类推，若各点的出次为w1w2wn如果w1n
37、1，w2n2，wk1n(k1)，但wknk(1kn)，则依次去掉k1个点，而不影响余下点的出次，此时余下点的出次n(k1)1nk若wknk，则必有wknk证毕4证明 设A与B出次相等，由于A、B必连有线，不妨设A胜B，于是A、B的出次不为0取所有负于B的点集M，设此集中有k个点，其中k必大于0于是负于A的点集中也有k个点，若M中没有点胜A，则M中的点均负于A，于是A胜M中所有点且胜B，即A的出次至少比B多1，与A、B出次相等矛盾故M中必有点C，C胜A，于是A胜B，B胜C，C胜A证毕 证明：不论何种比赛结果，所有参赛者出次的和都等于12(n1)n(n1)若每个参赛者的出次都互不相同，则出次分别为
38、0，1，2，n1此时不存在满足“A胜B，B胜C，C又胜A”的三个参赛者此时www02+12+(n1)2当有两个参赛者的出次相同时，就存在三角形回路设出次为wk的点为Ak设w1w2w1且设w1n1，wk1n(k1)，但wknk，则wknk，逐个把A1，A2，Ak1去掉，这样做不会影响剩下点的出次这样去掉点后，余下点中必有引向Ak的线，设从Aj(jk)有引向Ak的线，把这条线的方向改变，则Ak的出次变为wk+1，而Aj的出次变为wj1此时(wk1)2(wj1)2ww2(wkwj)2ww，即这样操作可使和www增加，继续这样做，直到使wknk，这时去掉wk，再做下去，直到每个wi都等于n(i1)(i
39、1，2，n)为止此时和式www已严格递增至这说明www成立5解 共计比赛6场，最多共可得18分若有三个队都是二胜一负得6分(如图中A、B、C队)，则不能保证一定出线(因要抽签才能决定是否出线)若一个队得7分，则保证一定出线，因不可能有三个队至少得7分，否则73=2118故得分不少于7分的至多有2个队故得到7分一定能出线ABCD6解 若三个队都互相打成平局，都输给另一队(图中B、C、D三队)，则此三个队都得2分，其中有一个队出线若某队只得1分，则该队1平2负，赢该队的两个队都至少得了3分，于是名次都在该队之前，该队不可能出线即某个队出线了，则该队至少得了2分7解 把相邻的两格中心用一条边相连，于
40、是就有一个8行，每行8个点的图，从88棋盘的左上角一格到右下角一格需要经过14条边，如果所有相邻方格中填入数的差小于5，则由于连填“1”的格与填“64”的格之间的路至多经过14条边于是这两格中数的差不会超过144=56.但641=63矛盾故结论成立8证明 当n1时，1条直线把平面分成两部分，用两色可以区分这两部分，如果增加1条直线，可以把这条直线某一旁的区域中原来涂的颜色变成另一种颜色则所有相邻的区域涂色都不同以后每多画出1条线都把线一旁的部分的每个区域中颜色重涂成与原来不同的颜色，就可使相邻区域涂色不同9解 设共有n个城市，每两个城市之间连一条线，每条线染三种颜色之一例如：汽车用红色，火车用
41、蓝色，飞机用黄色已知没有任何一点引出3种颜色的线且不存在同色三角形首先证明：任一点不能连出3条同色线，否则，设AB、AC、AD连红线，则B、C、D间都不能连红线设BC连蓝线，由于B只能连出两种颜色，故BD只能是蓝色线，此时，C、D都连了红蓝两色线，它们之间无论连红线还是蓝线均出现同色三角形于是每点引出的同色线不超过2条，线的颜色不超过2种，即不能超过4条线即城市数5若城市数5由于每点都引出某色线2条，另一色线2条，设AB、AC红色，AD、AE蓝色，由于B应引出2条红色，现BA红，故还要引出1条红线，BC不能红色(出现同色三角形)，故BE红由于EA、EB一红一蓝，故E应引出2红2蓝，由于ED不能
42、蓝，故ED红EC蓝，此时C、D都用了2色，从而它们也只能用红蓝两色，于是B也只能用红蓝两色，与要用3色矛盾若城市数4可以构成满足条件的图10解法1 按顶点颜色分类，三角形共有10类：三红，两红一蓝，两红一黑，一红两蓝，一红两黑，红蓝黑，三蓝，两蓝一黑，一蓝两黑，三黑按线段两端颜色分类，线段共有6类：红红，红蓝，红黑，蓝蓝，蓝黑，黑黑现在统计两端分别为红、蓝的边，在两红一蓝或两蓝一红这两类三角形中，每个三角形都有2条红蓝边，每个红蓝黑三角形都有1条红蓝边，设前两类三角形共有p 个，后一类三角形共有q个则两端红蓝的边共有2pq条而每条两端红蓝的边，在大三角形内的红蓝边设有k条，每条都被计算了2次，
43、大三角形的红蓝边有1条，计算了1次故2pq2k1，于是q0，即红蓝黑三角形至少有1个解法2 在每个划出的小三角形内取一个点，在三角形形外也取一个点如果两个三角形有一条红蓝的公共边，则在相应点间连一条线于是得到了图G，此时，两红一蓝或两蓝一红的三角形都是图G的偶顶点，而红蓝黑三角形则对应着图G的奇顶点，大三角形外的那个顶点也是奇顶点，由奇顶点的成对性，知图G中至少还有一个奇顶点，于是，至少还有一个红蓝黑三角形11证明：每个异色K3的三个角中必有两个角的两边异色，即每个异色三角形对应2个异色角反之每个异色角都在一个异色三角形内设第i个顶点引出了xi(0xi5，i=1，2，3，4，5，6)条红边，5
44、xi条蓝边则该顶点为顶点的异色角共有xi(5xi)个当xi=2或3时xi(5xi)=6取得最大值故异色三角形数662=18个但K6中共可连出C=20个三角形，即至少有2018=2个同色三角形存在只有2个同色三角形的二染色K6，把6点分成两组，每组3点，同组连红线，不同组连蓝线由于任取三点，必有两点同组，于是必有红线，但如有不同组的点，则必有蓝线 12解 共有C=210条航线，而每个航空公司有C=10条航线，故至少要21家航空公司画一个21边形，用顶点表示城市，依次编为121号取一个五边形它可以由连1，3，8，9，12这五个点而成其边及对角线分别对着分圆为1，2，3，4，5，6，7，8，9，11等分的弧这个五边形的边长互不重复，且含有了该正21边形的边及对角线的所有长度让这个五边形每次旋转1等分，旋转k次所在的五个点即为第k家公司所在的城市每个长度的对角线总会在某次旋转中出现于是相应城市间的航线存在
