灵魂尽头-幼儿园中班月总结

第67讲 图论问题(一)
本节主要内容是：把一个具体问题用图形表示出来，利用图 形的直观性可能更有利于问
题的解决．
有关的一些概念：由若干个不同的点及连接其中某些点 对的线所组成的图形就称为图．图
中的点的集合称为图的点集，记为V：V＝{v
1
， v
2
，…，v
n
，…}；图中的线的集合称为图的线
集(边的集合) ，记为E：E＝{v
i
v
j
}(v
i
，v
j
∈V)．故一个图由其点集V和线集E所决定，若用G
表示图，则记为G＝G(V；E)．含有n个点 的图称为n阶图．
在一个图中，如果某点v共连了k条线，则说此点的“次数”(或“度数”)为k， 记为degv＝
k.如果一个p阶图的每两个顶点间都连且只连了1条线，则称该图为p阶完全图，记为 K
p
．
若对每条线确定一个方向(即确定了线的两个端点中一个为“起点”，另一个 为“终点”．这时，
线是点的“有序对”)，则得到“有向图”；对有向图的一个顶点v，degv＝k ，若v是其中n条边
的起点，m条边的终点(m＋n＝k)，则称v的出次为n，入次为m．
链：若在一个图G＝(V；E)中取n+1个顶点 v
1
、v
2
、… 、v
n+1
，每两个相邻的顶点v
i
、
v
i+1
间 连有一条边l
i
,则边l
1
,l
2
,…,l
n就称为从v
1
到v
n+1
的一条链．n称为链的长度．

A类例题
例1⑴证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着 乙认
识甲)．
⑵ K
6
的边染成红蓝两色，求证：其中必有两个三角形，其三边同色．
分析 ⑴以点表 示人，连红、蓝两色的线分别表示“认识”与“不认识”，问题转化成图
的问题．要会把题目的语言转译 成图的语言：“三人互相认识”就表示三点间都连红线，“三
人互不认识”就表示三点间都连蓝线．⑵ 考虑每个异色三角形的三个角，其中两个角是异色
角，而同色三角形的三个角都是同色角．
证 明⑴用6个点v
1
，v
2
，…，v
6
表示这6个人，如果某 两人相互认识，则在表示此二人
的点间连一条红线，否则连一条蓝线．于是问题转化为证明此6点间一定 连出了三边均为红
色或蓝色的三角形．
在点v
1
连出的5条线中，由抽屉原 理知，必有某色线连有3条或3条以上．不妨设红线
连了至少3条．设v
1
与v
2
、v
3
、v
4
连的红线．现考虑点v
2
、v< br>3
、v
4
连线的情况，如果此三点
间有任两点连的红线，则出现红色三 角形(例如v
2
v
3
连红线，则v
1
v
2
v
3
是红色三角形)，如果这
三点间都不连红线，则出现蓝色三角形(v
2< br>v
3
v
4
是蓝色三角形)．故证．
⑵ 考虑K
6< br>共连了C
6
＝15条线，共得到C
6
＝20个三角形．设第i个顶点连 了r
i
(0≤i≤5)
条红线，5－r
i
条蓝线．由于r
i
(5－r
i
)≤6．所以，连出的异色角个数≤6×6＝36个．由于每个
异 色的三角形有2个异色角，所以图中异色三角形个数≤18，故图中同色三角形个数≥20－
18＝2．
说明 题⑴是早期匈牙利的一个图论竞赛题．解这类“实际问题”时，重要的是会用图的
语言解 释题意，把实际问题改写为图的问题．
⑵ 用异色角来解相关问题是较好的方法．

例2由5人组成一个公司，其中任意三人总有2人彼此认识，也总有2人彼此不认识．证
明：这五人可 以围桌而坐，使每人两旁都是他认识的人．(1978年保加利亚数学竞赛)
证明 用5个点表示这5 个人，若两人互相认识，则在表示这2个人的点间连1条线．题
23

目的条件即 是：任三点间至少连1条线，但不能连3条线．
首先，每点都至少连了2条线，若点v
1只连出1条线，则它至少与某三点(设为v
2
、v
3
、
v
4
)未连线，则此3点间都要连线(若v
2
与v
3
没有连线，则v
1
与v
2
、v
3
就都
没有连线，与已知矛盾)．出 现了以v
2
、v
3
、v
4
为顶点的三角形，矛盾．
其次，若某点连出了3条线，则此三点间都不能连线，与已知矛盾．
故知：每点都恰连2条线 ．它不能连成三角形，也不能连成四边形，否
则余下的点无法连线，故只能如图所示，证毕．
说明 仔细体会上述两例的特点，明白什么时候应该用图来解相关的题：当涉及多个元素
的某些 相互关系时，就可能用图来解释．

情景再现

1．在例1中，把6个人改为5个人，结论是否一定成立？
2．图G有n个顶点，n+1条边，证明：图G至少有一个顶点的次数≥3．

B类例题

例3设竞赛图(每两个点都连了1条线的有向图)中，点A
k的出次与入次分别为w
k
与e
k
(k
＝1，2，…，n)，
证明 w
1
＋w
2
＋…＋w
n
＝e
1＋e
2
＋…＋e
n
．
分析根据竞赛图的特点可知：⑴ 每点的出次与入次的和都等于n－1，⑵ 所有点的出次
1
的和与入次的和相等．由此可以推出 ：所有点的出次和与入次和都等于n(n－1)．这是两个基
2
本的性质．在要证的式子中把e
k
用n－1－w
k
代替．
证明对于每个点，出次与入次的和都是n－1，即
w
k
＋e
k
＝n－1(k＝1，2，…，n)， ①
所有出次的和与所有入次的和相等，且都等于图中弧的条数：
1
w
1
＋w
2
＋…＋w
n
＝e
1
＋e
2
＋…＋ e
n
＝
2
n(n－1)．②
所以 e
1
＋e
2
＋…＋e
n

＝(n－1－w
1
)
2
＋(n－1－w
2
)
2
＋…＋(n－1－w
n
)
2

＝n(n－1)
2
＋w
1
＋w
2
＋…＋w
n
－2(w
1
＋w
2
＋ …＋w
n
)(n－1)
1
22
2
＝w
1
＋w
2
＋…＋w
n
＋n(n－1)
2
－2
2(n－1)(n－1)
＝ w
1
＋w
2
＋…＋w
n
．
说明 本题的证明方法与《奇偶分析》中的例6相似．

例4平面上给定7个点，用一些线段连接它 们，每三个点中至少有两点相连，问至少要
有多少条线段？试给出一个图．(1989蒙古数学竞赛)
分析首先找到连线条数的下界(即至少要连出多少条线)，再寻找是否可能达到这个下界，
22
2
22
2
22
2
22
2
22
2< /p>

可以分别枚举可能的连线方法，讨论每种方法的连线条数，得到最小的结果．
解 7个点中共有三点组C
7
=35个．每条线段共与其余5点组成5个三角形．故线段条数
≥
35
＝7条．
5
A
3
如果有一个点没有连线，则其余 6点两两都必须连
B
C
线，要C
6
＝15条．
连线数＞C
5
＝10
2
2
如果有一点只连了一条线，其余5点必须两两连线，< br>条．
设某点只连了2条线，如点A只连了AB、AC这2条线，则其余4点均未与A连线，于
是它们必须两两互连，应连C
4
=＝6条．此时，取B、C两点及其余4点中的任一点 ，尚不满
足条件，故BC应连线，此时连了9条线，所得图形满足题目要求．
21
若 每点都至少连出3条线，则总度数≥21，即至少连了[
2
]+1＝11条线．
所以，至少连9条线．

例5九名数学家在一次国际会议上相遇，发现他们中的任三 人中至少有两人能用同一种语
言对话，如果每个数学家至多会用三种语言．证明：至少有三人可用同一种 语言对话．(1978
年美国数学竞赛)
分析 9个人用9个点表示．证法1中，多种语言则 用多种颜色的线来表示，转译结论“三
人可用同一种语言对话”时，应注意：如果从一点向另两点连出了 同色的两条线，表示另两
人也能用相应的语言对话，从而就出现了同色三角形．所以，只要证明从一点一 定引出了同
色的线即可．而在证法2中，改设若二人不能对话就连1条线(即不存在二人都会的语言)． 此
时结论就应转译为“存在三点，两两都没有连线”．
证法1用9个点表示这9个人，某二人 如能用第r种语言交谈，则在表示此二人的点间连
一条线，并涂上第r种颜色，于是，本题即是证明，存 在一个同色的三角形．
首先，若v
1
与v
2
、v
1
与v
3
间都连了第k种颜色线，则v
2
与v
3
间也要连第 k种颜色线．此
时即出现同色的三角形．所以只要证明从其中某一点出发的线中必有两条线的颜色相同．
反设从任一点出发的线中没有同色的线，由于每个人至多会用三种语言．即degv
i
≤3，
于是v
1
至少与5个点不邻接，设为v
2
、…、v
6
，同样，v
2
至少与5个点不相邻接，于是v
3
、…、
v< br>6
中至少有一点与v
2
不相邻接．设为v
3
，于是v
1
、v
2
、v
3
不相邻接．与已知“任三人中都至
少有两人 能用同一种语言对话”矛盾．故证．
证法2取9个点v
1
，v
2
， …，v
9
表示9个人，如果某二人不能对话，则在表示此二人的点
间连一条线，于是在 任何三点间，都有两个点不相邻，即不存在三角形．
如果有人至少与4个点不连线，由于他最多只能讲 三种语言，则他必与其中某两人讲同
一种语言．于是相应三人可以用同一种语言来对话．
下面 证明存在一点，其度不大于4．从而该点至少与4点不相邻．如果degv
1
≤4，则v
1
即为所求．若degv
1
＞4，则至少degv
1
＝5，即至少 有5个点与之连线，设为v
2
，…，v
6
，由
于这些点不能连出三角 形，故v
2
，…，v
6
的任何两个之间都不能连线，从而v
2
与v
3
，…，v
6
均无连线，于是degv
2
≤4．即可 证得原题．
说明两点间连了1条线，则说这两点相邻．
本题的两种证明方法从两个方向出发 ，一种是两人可用同一种语言通话，就在相应两点间
2

连一条边，证法2是反过 来，两人不能通话时则连一条边，都能应用图解决问题．

例6 俱乐部里有14个人想打桥 牌，已知过去每个人都与其中的5个人合作过，现在规定
4个人中必须任两个人都没有合作过才准许在一 起打1局桥牌，这样打了3局就无法再打下去
了，如果这时又来了一人，他与原来的14个人都没有合作 过，证明：一定可以再打1局．
分析 打桥牌时，4人分成合作的两对，合作的两人坐在相对的位置打牌．于是每局桥牌，
都有两对人合作．
把题目的条件与结论都转述为图的语言，并找出结论的等价命题是：找到三个人互相都没
有合作 过，即存在3个点互不相邻．
证明 用14个点表示这14个人，若某两人合作过，则在表示这两人的 点间连一条线，于
是，题目条件即：其中每个点都已连出了5条线，且在此14个点中，可以找出3组点 (每组4
个点)，这三组点间，两两未连线，若这3组点之间共连出6条线后，对于任意4点，都至少< br>有两点连了线．(14个点间一共连了41条线)，证明此时一定存在3个点，两两都没有连线(从
而添入第15个点后，可与此3点合成4点，两两无连线)．
由于14个点中的每个点原来都与(1 4－1－5＝)8个点不相邻．在又打3局连出了6条边以
后，至多有12个点又连了线，所以至少还有 2个点，每个点仍与8个点不相邻．设其中一点
为v
1
．与v
1
不相 邻的点集为S．
下面证明：S中必有一点v
2
至少与7个点不相邻．反设不存在这样 的点，则此8点中，每
个点都至多与6个点不相邻，故此8个点都至少连了(14－6－1＝)7条边， 于是此8点中的每
个点又都新连了至少2条边，故又新连出了8×2÷2＝8条边(除以2是因为每条边 可能在两个
点端点处被计算了2次)．这与只连了6条边矛盾，所以存在S中的一点v
2
，至少与7个点不
相邻．
但8+7＝15＞14，必有一点v
3
与v1
，v
2
均未连线．此三点即为所求．
链接v
3
存在 是根据容斥原理：把这14个人的集合记为S，与v
1
相邻的点集记为A，与
v
2
相邻的点集记为B，则A∪BS．故
card(A∪B)≤card(S)．
而 card(A∪B)＝card(A)＋card(B)－card(A∩B)，
故 card(A)＋card(B)－card(A∩B)≤card(S)，
现card(A)＋card(B)＝15，card(S)＝14，于是card(A∩B)＞0．

情景再现

3．⑴右面的有向图由4个顶点及一些弧(有向线
D
的出次(引出的弧的条数)与入次(引入的弧的条数)．
⑵求出上题中所有各点的出次的和与入次的和，
A
什么关系？
⑶证明：任一有向图中，出次的和与入次的和相等．
4．在n(n≥3)个点的竞赛图中，一定有两个点的出次相同吗？
C 段)组成，指出各点
B
它们与弧的条数有

5．在集合S的元素之间引入关系“→”．⑴ 对于任意两个元素a，b∈S，要么a→b，
要么b→a，二者有且只有一个成立；⑵ 对任意三个元素 a，b，c，如果a→b，b→c，则c
→a．问集合S中最多能有多少个元素？(1972年英国数学 竞赛)
6．证明：⑴ 如果竞赛图中各点的出次不等， 那么可将这些点排成一列，排在前面的点有弧到达排在后面的任一点(即排在前面的选手胜排在后面的所有选手)．
⑵ 如果点数n≥3的竞赛图中有三角形回路，那么，图中必有两点的出次相等．

C类例题 < br>例7某足球赛有16个城市参加，每市派出2个队，根据比赛规则，每两队之间至多赛一
场，同城 两队之间不进行比赛．赛过一段时间后，发现除A城甲队外，其他各队已赛过的场
数各不相同．问A城乙 队已赛过几场?证明你的结论．
分析注意分析“各队赛过场次各不相同”的含义，即能推知比赛场次的 取值情况．再从
比赛场次最多的队开始讨论，与之比赛的队是哪些队？
A城
证明 用 32个点表示这32个队，如果某两队比赛了一场，
30
甲队
0
1
2
则在表示这两个队的点间连一条线．否则就不
28
29
连线．
3< br>由于，这些队比赛场次最多30场，最少0场，共有31种情
况，现除A城甲队外还有31个队， 这31个队比赛场次互不相
同，故这31个队比赛的场次恰好从0到30都有．就在表示每个
队 的点旁注上这队的比赛场次．
考虑比赛场次为30的队，这个队除自己与同城的队外，与不
1 6
15
14
同城的队都进行了比赛，于是，它只可能与比赛0场的队同城；
A 城
再考虑比赛29场的队，这个队除与同城队及比赛0场、1场(只赛
乙队
1场的队已 经与比赛30场的队赛过1场，故不再与其它队比赛)
的队不比赛外，与其余各队都比赛，故它与比赛1 场的队同城；依次类推，知比赛k场的队
与比赛30－k场的队同城，这样，把各城都配对后，只有比赛 15场的队没有与其余的队同城，
故比赛15场的队就是A城乙队．即A城乙队比赛了15场．
说明 有些题的已知条件讨论起来头绪纷繁，如果利用图来讨论则可以化繁为简．利用点
与线的 相邻与否来研究这一类题目需要一定的技巧，也需要相当的抽象概括能力与逻辑推理
能力．请大家多做些 练习．

例8n(n＞3)名乒乓球选手单打若干场后，任意两个选手已赛过的对手恰好都不 完全相同，
试证明：总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然< br>都不完全相同．(1987年全国高中数学联赛)
分析 本题的求证暗示要用反证法，设去掉任 一个选手，都会有两个选手赛过的对手完全
相同．于是这两人组成一个点对．这样就会得到n个点对．每 个点对连一条线，n个点连出了
n条线，就可用图的性质得到圈，使问题得证．这是证法1的思路．
每个选手的对手可以组成集合，研究对手集的性质，用最小数原理来证明，这是证法2
的思路．
证法1把这些选手编为1至n号，以n个点表示这n个人，各点也相应编为1至n号．
反设去 掉任何一个选手后，都有两个选手的已赛过的对手完全相同．于是，如果先去掉1
号选手，则有两个选手 的已赛过的对手完全相同，设为第i号与第j号，在表示此二人的点间
连一条线，并在线上注上“1号” ．这说明，此二人在去掉1号选手之前必是一人与1号赛过，
另一人与1号没有赛过．而且不可能在去掉 1号后有三人都相同，否则，此三人与1号选手

比赛的情况只有两种：赛过或没有赛过， 如果去掉1号后，此三人的情况完全相同，则去掉1
号之前必有2人赛过的对手完全相同．(如果去掉1 号后有不止一对选手的已赛过对手完全相
同，则只任取其中的一对连线，其余的对则不连线．)
同样，如果再依次去掉2号、3号，…，直至n号，每去掉1个选手，都会在某两点之
间连1条线．这 样，就在n个点间连了n条线．且这些线上分别注了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)表示

(B)

(D)
A、B已赛过的对手集合．显然，若A∈α(B)，则B∈
A=E

(C)
C
α(A)．

(E)=

(A)
设A是对手集中元素最多的的选手．
D
B
若命题不成立，则存在两个选手B、C使去掉A后，
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)，故D≠A：又D∈α(C)，故D∈α(B)，即B∈α(D) ＝ α(E)∪{C}，
从而B∈α(E)，Cα(E)，而去掉A后，B、C的对手集相同，从而E＝A ．
于是α(A) ＝α(E) ＝α(D){C}，即α(A)比α(D)少一个元素C，这与A是“ 对手集中元素
最多的”矛盾．故证．
说明 证法1是根据如下结论：如果n个点间连了n条线 ，则必出现“圈”：即从某一点
出发，沿边前进，最后还能回到出发点．
证法2用最小数原理对集合的元素进行讨论，较难理解，可对照图理解相应的结论．
链接 树与圈
若在一个图G=(V；E)中取n+1个顶点 v
1
、v
2
、…、v
n+1
，每两个相
邻的顶点v
i
、v
i+1
间连有一条边l
i
,则边l
1
,l
2
,…,l
n
就称为从v
1
到v
n+1
的
一条链．一个图中的任意两个顶 点间如果都有一条链，该图就是连通
的．一条链的两个端点v
1
与v
n+1< br>重合时，就称为圈．没有圈的连通
图称为树．n阶树可以记为T
n
．在一个图中 ，次数为1的顶点称为悬
挂点．
定理1 如果树T的顶点数≥2，那么，它至少有两个悬挂点．

从树的任何一个顶点出发，沿某 个方向前进，已走过的边不重复
走，由于树是无圈的，故每个顶点至多走过1次，如果，经过的一个顶点不是悬挂点，则还可以前进到下一个顶点，由于树的顶点只有有
限个，故前进到某个顶点(如果 图中共有n个顶点，则至多前进n－1
步)后就无法再继续前进，即到达一个次数为1的顶点．此顶点即 为
一个悬挂点．再从此悬挂点出发，沿链走一次(第一步是按刚才的反
方向前进)，则又可以到 达一个悬挂点．此悬挂点与刚才第一个悬挂
点不同．即图中至少有两个悬挂点．
定理2一个n阶的连通图是1个树，当且仅当它有n－1条边．
先证明：如果树T的顶点数为n，则其边数为n－1．
证明 对于n＝1或2，定理显然成立．
设定理对于k个顶点时成立，即若一个树有k个顶点，则其边有k－1条．对于k+1个顶点的树，只要去掉一个悬挂点及与之相邻的
一条边，就成为有k个顶点的 情形，此时的树有k个顶点与k－1条
边，此时再把去掉的1个顶点及1条边添入，就成为k+1个顶点 ，k
条边的树．故证．
再证明：如果图G是连通的，且有n个顶点与n－1条边，则G
是一个树．
取G的生 成树T，则此生成树有n个顶点，因是树，故有n－1
条边．但TG，故T＝G．故证．
定理3 树T具有以下性质：
⑴ 在T中去掉任一边后，所得的图是不连通的；

⑵ 在T中添上1条边后，所得的图有圈；
⑶T中的任两个顶点v
1
与v
2
间有且仅有1条链．
证明 ⑴ 设树T有n个顶点与n－1条边，在T中去掉1条边后得
到图G，如果G仍连通，则G仍是一个树( 因无圈且连通)．应有n－
1条边，矛盾．
⑵ 如添上1边后仍无圈，则仍为树，有n个顶点与n条边，矛盾．
⑶ 由T连通，故v
1
与v
2
间必有链，若v
1
与v
2
间有不完全相同的
两条链，则此图中有圈，即不是树．矛盾，故v
1
与v
2
间有且仅有1条链．
情景再现

7．某个团体有1982个人，其中任意4人都至少有一人 认识其他三个人，认识其他所有
人的人数最少是多少？(1982年美国数学竞赛)
8．⑴在 一所房子里有10个人，其中任意3人中至少有2人互相认识，证明：其中有4
人，他们任意2人都互相 认识．(1980英国数学竞赛)
⑵如果把⑴中的数10改为9，结论仍成立否？(1977年波兰数学竞赛)

习题
13
1．如果每个点的出次都是2，那么，一个点经过两条弧就可以到达的点至 多有几个？经过
一条弧或两条弧可以到达的点至多有几个？
2．在竞赛图中必有一个点，从它到其它的顶点，只需经过一条弧或两条弧．
3．一个有n个 点的竞赛图，各点的出次为w
1
≥w
2
≥…≥w
n
．如果w
1
＝n－1，w
2
＝n－2，…，
w
k
－
1
＝n－(k－1)，但w
k
≠n－k(1≤k≤n)．证明：w
k
＜n－k．
4．⑴ 如果在点数n≥3的竞赛图中，有两个点的出次相等．证明，图中必有三角形回路
(即有三个选手A、B、C，其中A胜B，B胜C，C又胜A)．
⑵ 在一个n人参加的循环 赛中，每两人比赛一场，如果没有平局，参赛者赢的场数分别
是w
1
，w
2< br>，…，w
n
．求证：出现三个参赛者A，B，C，满足A胜B，B胜C，C胜A的充分< br>必要条件是
22
2
(n－1)n(2n－1)
w
1
＋w
2
＋…＋w
n
＜．
6
5．亚洲区足球小组赛，每组有 4个队，进行循环赛，每两个队赛一场，胜者得3分，负
者得0分，平局各得1分，赛完后，得分最高的 前两名出线．如果几个队得分相同，那么便
抽签决定这些队的名次，问一个队至少要得多少分，才能保证 一定出线？
6．条件同上题，问一个队如果出了线，它至少得了多少分？

7．在8×8棋盘上填入1～64的所有整数，每格一数，每数只填一次， 证明：总可以找
到两个相邻的方格（具有公共边的两个方格叫相邻）， 在此两个方格中填入的数的差不小于
5？
8．平面上有n条直线，把平面分成若干个区域.证 明:用两色就足以使相邻的区域都涂上
不同的颜色.
9．在某个国家，任意两个城市之间用下 列交通工具之一进行联络：汽车，火车和飞机．已
知没有一个城市拥有这三种交通工具，并且不存在这样 三个城市，其中任意两个在联络时都
用同一种交通工具．而且这个国家用了这三种工具．这个国家最多有 多少个城市？(1981年保
加利亚，美国数学竞赛)
10．一个大三角形的三个顶点分别涂 红、黑、兰三色，在三角形内部取若干点也任意涂
红、黑、兰三色之一，这些点间连有一 些线段，把大 三角形分成若干互相没有重叠部分的一
些小三角形.求证:不论怎样涂，都有一个小三角形，其三个顶点 涂的颜色全不同.
11．证明：在2色K
6
中一定存在两个同色三角形（即同色K< br>3
）．
12．某个国家有21个城市，由若干个航空公司担负着这些城市之间的空运任 务．每家公
司都在5个城市之间设有直达航线(无需着陆，且两城市间允许有几家航空公司的航线)，而 每
两个城市之间都至少有一条直达航线．问至少应有多少家航空公司？(1988年前苏联数学竞
赛)

本节“情景再现”解答：
1．解 如图的5个点即不存在同色三角形，故例2中把6个人改为5个人后，结论可能不
再成立．
2．证明 计算每个顶点引出的边的条数(次数)，如果每个顶点的
次数都≤2，则统计得到的 边数≤2n，但每条边都被统计过2次，故应
统计得到边数=2(n+1)．矛盾．故至少有一个顶点， 其次数≥3．
3．解 ⑴点A：出次3，入次1；点B：出次1，入次1；点C：出
次0，入次2；点D：出次1，入次1．
⑵ 出次的和=3+1+0+1=5；入次的和=1+1+2+1=5．
出次的和=入次的和．
⑶证明 由于每条弧起点所是出次的点，终点都是入次的点，故出次和与入次和相等，都
等于弧的条数．
4．解 不一定，例如右面的一个图中，就没有两个点的出次相
B
A
同．A、B、C、D四点的出次依次为3，2，1，0．
一般的n个点的竞赛图中，可以出现n个点的出次分别为n－1，n
C D
－2，n－3，…，2，1，0这n个值，于是不一定有两个点的出次相
同．
5．解 S中有3个元素是可以的，a→b→c→a．满足要求．
若S至少有4个元素，取其中4点，由⑴， S中每两点间都要连出1条有向线段，4点
间连出6条有向线段．每条有向线段都记一个出次，共有6个 出次．因此至少有一个点至少
有2个出次．设a→b，a→c，则无论b→c或是c→b均引出矛盾．即 S的元素个数≤3．故
S最多有3个元素．
6．证明 ⑴ 设共有n个点，由于各点出次互 不相等，故这n个点的出次取得0，1，2，…，
n－1这n－1个值中的每个值．
把出次为 0的点排在最后，其余各点均到达此点．出次为1的点必到达此点，由于出次
为1的点只到达1个点，故 出次为1的点只到达出次为0的点，把出次为1的点排在倒数第

二位；再考虑出次为2的 点，由于此点只到达2个点，故它只到达已排的两个点而不能到达
其余的点，把出次为2的点排在倒数第 3位；……，依此类推，把出次为k的点排在倒数第
k+1位，直到出次为n－1的点排在第1位．这就 得到满足题目要求的排法．
⑵ 反设图中所有各点的出次均互不相等，则由上题，可把这些点排成一列 ，使前面的点
到达后面的点．而后面的点不能到达前面的点，于是该图中没有回路，与已知此图有回路矛
盾．故必有两点出次相等．
7．解 先证明：任意4人中都有1人与其余n－1人认识． < br>用n个点表示这n个人，若两个人认识，则在表示
V
1
'
这两个人的点 间连一条实线，否则连一条虚线．
V
4
'
V
2
'
V
1
V
1
V
2
V
3
设任取4人v
1
、v
2
、v
3
、v
4
，其中v
1
与v
2
、v
3
、v
4
都认
V
4
V
2
识，但此四人中无人与n－1人都认识．即每个点都有
V
3
V< br>1
'
与之不相邻的点．设与v
1
、v
2
、v
3
、v
4
不相邻的点分别为
V
3
'
2
1
v
1
΄、v
2
΄、v
3
΄、v
4< br>΄，显然v
1
΄≠v
2
，v
2
΄≠v
1，若v
1
΄≠v
2
΄，则四点
图6
v
1
、v
2
、v
1
΄、v
2
΄不满足题意．于是v
1
΄=v
2
΄，同理v
1
΄=v
3
΄，于是
得v
1
΄=v
2
΄=v
3
΄，此时v
1
、 v
2
、v
3
、v
1
΄这四点仍不满足已知条件．故证．
又证 设图G中度数小于n－1的点为v
1
、v
2
、…、v
k
，记F={v
1
、v
2
、…、v
k
}，用实线表
示相邻(认识)，用虚线表示不相邻．
若k＜4，则命题正确(因为图中找不到4个人，他们中任1人都没有与其余n－1人认识)．
若k≥4，由于v
k+1
、v
k+2
、…、v
n
V
2
V
1
V
2
V
1
V
2
V
1
的度数都=n－1，故与v
1
不相邻的点都
在F中，设为v
2< br>，此时若还能找到v
3
、
V
4
V
4
V
3
V
4
V
3
V
3
23
1< br>v
4
∈F，且v
3
与v
4
不相邻．则此四人
图7
不满足题目要求(图7⑴)．若在F中除
v
1
、v
2
外 无不相邻的人，则v
3
、…、v
k
均至少与v
1
、v
2
中某一人不相邻．则如图⑵、⑶，亦与
已知矛盾．故k≥4不可能．故证．
再考 虑本题：把1982个人中的任意4人组成一组，该组中必有1人认识其余所有的人．去
掉这个人，在余 下的人中再任取4人，又成一组，又可找出一个认识其余所有人的人；…，
这样一直做下去．直到余下3 人为止，此3人可能与其余的人不全认识．
故至少有1979人认识其余所有的人．
8．解 ⑴用10个点表示这10个人，如果某2人互相认识，则在表示这两人的点间连1
条线．
即任3点都至少连了1条线，要求证明存在一个K
4
．
设不存在K
4
，即任意4点中总有2点没有连线，
A
6
① 设某一点A与4点都没有连线，则由假设此4点中有2
A
A
5
点未连线，则此 2点与A共3点均未连线，与题设矛盾．故A至
多与3点未连线，即至少与6点连了线．
A
4
② 设A与A
1
、A
2
、…，A
6< br>连线，则A
1
，…，A
6
中任意3点
A
1
必 有2点未连线，否则存在K
4
，
A
3
③ 设A
1
与B
i
、B
j
、B
k
都未连线，则B
i
、 B
j
、B
k
间若有两点
A
2
未连线，则出现3点， 都未连线，与已知矛盾．故此三点间都连
了线，于是此三点与A成为K
4
．
④ 由③知A
1
，…，A
6
中任一点至多与其余5点中的2点未连线 ．即与其余5点中至少3
点连了线．设A
1
与A
2
、A
3< br>、A
4
连了线．此时A
2
、A
3
、A
4间至少连了1条线，设A
2
A
3
连了
线，则A、A
1< br>、A
2
、A
3
成为K
4
．

由上证可知，不存在K
4
的假设不成立．
⑵ 若有某点连出6条线，则如上证．
若每点连线数＜6，当每点连线数都=5时．此时9个点连线统计为45，为奇数．不可能．
若有某点连线数＜5，即该点至少与4点未连线，则如上①，矛盾．从而必有点连线数＝
6的点．

“习题67”解答：
1．解 一个点经过两条弧就能到达的点至多有4个．经过一 条弧或两条弧就能到达的点至
多有6个．如图，每个点的出次都是2，点A经过1A 条弧能到达B、
C，点B、C分别经过1条弧可以到达D、E、F、G，故点A经过1条
C
B
或2条弧可以到达至多6个点．其中如果有些点重合，则点A可以到达
的点就少于6个．
G
D E
F
1
2．证明 取出次最多的点为A，则A的出次≥
2
(n－1)．他可以经
1
一条线到达的点为B
1
，B2
，…，B
m
，m≥
2
(n－1)．对于A不能到达的点C，若 B
1
，B
2
，…，
B
m
中没有点到达C，则不能到 达C的点至少有m+1个，即C的出次比A多，与A为出次最
多的点矛盾．故所有A不能到达的点，都可 经2条线到达．故证．
3．证明 k＝1时，若w
1
≠n－1，则w
1
＜n－1．
设w
1< br>＝n－1，即w
1
到达所有其余的点．把出次为w
1
的点去掉，这对余 下的点的出次都
不受影响．此时就得到一个只有n－1个点的竞赛图．若w
2
≠n－2 ，则w
2
＜n－2．
设w
1
＝n－1，w
2
＝n －2，同上两次去掉出次为w
1
，w
2
的点，则得到一个有n－2个点的竞赛图．其中每个点的出次≤n－3．于是若w
3
≠n－3，就有w
3
＜ n－3．
依此类推，若各点的出次为w
1
≥w
2
≥…≥w
n
．如果w
1
＝n－1，w
2
＝n－2，…，w
k
－
1
＝n
－(k－1)，但w
k
≠n－k(1≤k≤n)，则依次去 掉k－1个点，而不影响余下点的出次，此时余下
点的出次≤n－(k－1)－1＝n－k．若w
k
≠n－k，则必有w
k
＜n－k．证毕．
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．证毕．
1
⑵证明：不论何种比赛结果，所有 参赛者出次的和都等于1＋2＋…＋(n－1)＝
2
n(n－1)．
若每个参赛者的 出次都互不相同，则出次分别为0，1，2，…，n－1．此时不存在满足
“A胜B，B胜C，C又胜A ”的三个参赛者．
(n－1)n(2n－1)
22
2
此时w
1＋w
2
＋…＋w
n
＝0
2
+1
2
+… +(n－1)
2
＝．
6
当有两个参赛者的出次相同时，就存在三角形回路． 设出次为w
k
的点为A
k
．
设w
1
≥w
2
≥…≥w
1
．且设w
1
＝n－1，…，w
k
－< br>1
＝n－(k－1)，但w
k
≠n－k，则w
k
＜n－
k，逐个把A
1
，A
2
，…，A
k
－
1
去掉，这样做不会影响剩下点的出次．这样去掉点后，余下点中
必有引向A
k
的线，设 从A
j
(j>k)有引向A
k
的线，把这条线的方向改变，则A
k< br>的出次变为w
k
+1，
而A
j
的出次变为w
j
－1．此时(w
k
＋1)
2
＋(w
j
－1)
2< br>＝w
k
＋w
j
＋2(w
k
－w
j
) ＋2＞w
k
＋w
j
，即这样
操作可使和w
1
＋w< br>2
＋…＋w
n
增加，继续这样做，直到使w
k
＝n－k，这时 去掉w
k
，再做下去，
22
2
2222

直到 每个w
i
都等于n－(i－1)(i＝1，2，…，n)为止．此时和式w
1
＋w
2
＋…＋w
n
已严格递增至
(n－1)n(2n－1)
22
2
(n－1)n(2n－1)
．这说明w＋w＋…＋w成立．
12n
＜
66
5．解 共计比赛6场，最多共可得18分．若有三个队都是二 胜一负得6分(如图中A、B、
C队)，则不能保证一定出线(因要抽签才能决定是否出线)．
若一个队得7分，则保证一定出线，因不可能有三个队至少得7分，否则7×3=21>18．故
得分 不少于7分的至多有2个队．故得到7分一定能出线．
6．解 若三个队都互相打成平局，都输给另一 队(图中B、C、D三队)，则此三个队都得
2分，其中有一个队出线．
B
A < br>若某队只得1分，则该队1平2负，赢该队的两个队都至少
得了3分，于是名次都在该队之前，该 队不可能出线．
即某个队出线了，则该队至少得了2分． C D
7．解把相邻的两格中心 用一条边相连，于是就有一个8行，
每行8个点的图，从88棋盘的左上角一格到右下角一格需要经过 14条边，如果所有相邻方
格中填入数的差小于5，则由于连填“1”的格与填“64”的格之间的路至 多经过14条边．于是这
两格中数的差不会超过144=56.但64－1=63．矛盾．故结论成立 ．
8．证明当n＝1时，1条直线把平面分成两部分，用两色可以区分这两部分，如果增加1
条直线，可以把这条直线某一旁的区域中原来涂的颜色变成另一种颜色．则所有相邻的区域
涂色都不同． 以后每多画出1条线都把线一旁的部分的每个区域中颜色重涂成与原来不同的
颜色，就可使相邻区域涂色 不同．
9．解 设共有n个城市，每两个城市之间连一条线，每条线染三种颜色之一．例如：汽
车用红色，火车用蓝色，飞机用黄色．已知没有任何一点引出3种颜色的线．且不存在同色
三角形．
AE
首先证明：任一点不能连出3条同色线，否则，设AB、AC、AD
连红线，则B 、C、D间都不能连红线．设BC连蓝线，由于B只能连出
D
B
两种颜色，故BD只能 是蓝色线，此时，C、D都连了红蓝两色线，它
C
们之间无论连红线还是蓝线均出现同色三角形 ．
于是每点引出的同色线不超过2条，线的颜色不超过2种，即不能超过4条线．即城市
数≤5．
若城市数＝5．由于每点都引出某色线2条，另一色线2条，设AB、AC红色，AD、AE
蓝 色，由于B应引出2条红色，现BA红，故还要引出1条红线，BC不能红色(出现同色三
角形)，故B E红．由于EA、EB一红一蓝，故E应引出2红2蓝，由于ED不能蓝，故ED
红．EC蓝，此时C、 D都用了2色，从而它们也只能用红蓝两色，于是B也只能用红蓝两色，
与要用3色矛盾．
若城市数＝4．可以构成满足条件的图．
10．解法1 按顶点颜色分类，三角形共有10类 ：三红，两红一蓝，两红一黑，一红两
蓝，一红两黑，红蓝黑，三蓝，两蓝一黑，一蓝两黑，三黑．按线 段两端颜色分类，线段共
有6类：红红，红蓝，红黑，蓝蓝，蓝黑，黑黑．
现在统计两端分别 为红、蓝的边，在两红一蓝或两蓝一红这两类三角形中，每个三角形
都有2条红蓝边，每个红蓝黑三角形 都有1条红蓝边，设前两类三角形共有p 个，后一类三
角形共有q个．则两端红蓝的边共有2p＋q条．
而每条两端红蓝的边，在大三 角形内的红蓝边设有k条，每条都被计算了2次，大三角形
的红蓝边有1条，计算了1次．故
22
2

2p＋q＝2k＋1，于是q≠0，即红蓝黑三角形至少有1个．
解法2 在每个划出的小三角形内取一个点，在三角形形外也取一个点．如果两个三角形
有一条 红蓝的公共边，则在相应点间连一条线．于是得到了图G，此时，两红一蓝或两蓝一
红的三角形都是图G 的偶顶点，而红蓝黑三角形则对应着图G的奇顶点，大三角形外的那个
顶点也是奇顶点，由奇顶点的成对 性，知图G中至少还有一个奇顶点，于是，至少还有一个
红蓝黑三角形．
11．证明：每个异 色K
3
的三个角中必有两个角的两边异色，即每个异色三角形对应2个
异色角．反之每 个异色角都在一个异色三角形内．设第i个顶点引出了x
i
(0≤x
i
≤5， i=1，2，
3，4，5，6)条红边，5－x
i
条蓝边．则该顶点为顶点的异色角共 有x
i
(5－x
i
)个．当x
i
=2或3
时xi
(5－x
i
)=6取得最大值．故异色三角形数≤6×6÷2=18个． 但K
6
中共可连出C
3
6
=20个三角形，即至少有20－18 =2个同色三角形．
存在只有2个同色三角形的二染色K
6
，把6点分成两组，每组 3点，同组连红线，不同
组连蓝线．由于任取三点，必有两点同组，于是必有红线，但如有不同组的点， 则必有蓝线．
12．解 共有C
21
=210条航线，而每个航空公司有C
5
=10条航线，故至少要21家航空公
司．
画一个21边形，用顶点表示城市，依 次
个五边形它可以由连1，3，8，9，12这五
对角线分别对着分圆为1，2，3，4，5， 6，
弧．这个五边形的边长互不重复，且含有了
对角线的所有长度．让这个五边形每次旋转在的五个点即为第k家公司所在的城市．每
会在某次旋转中出现．于是相应城市间的航



编为1~21号．取一
个点而成．其边及
7，8，9，11等分 的
该正21边形的边及
1等分，旋转k次所
个长度的对角线总
线存在． 22
20
21
1
2
3
4
5
6
19
18
17
16
15
O
9
7
14
8
13
12
11
10