题目内容
【题目】有2013位来自不同国家的代表参加一个会议，每位代表都懂得若干种语言，已知其中任意四位代表之间都可进行交谈而不需要此四位代表以外的其他人帮助，即此四人中的任意两人都能讲同一种语言而实现直接沟通，或者通过第三个人的翻译实现间接沟通，或者通过他们各自的翻译能讲的同一种语言实现低效的间接沟通，证明：可以将所有代表分配住进671个房间，每个房间住3人，使得每个房间的3人都可以交谈。
【答案】见解析
【解析】
首先证明两个引理.
引理1 4阶连通图
中有三点组成连通子图.
引理1的证明：由的连通性知其存在生成树，将该树去掉一个悬挂点，得到三点连通子图.
引理2 若6阶图的任意四阶子图都连通，则可以按顶点划分为两个连通的三阶子图.
引理2的证明：显然，为连通图.
考虑的生成树
.
（1）若至少有4个悬挂点
、
、
、
，由引理1知其中存在三点组成连通子图，生成树去掉这三点后仍连通，故结论成立.
（2）若的悬挂点不多于
个，只有如图的两种情形，均使结论成立.
回到原题：
由引理1，选出四个人，其中必有三人可交流，安排同一房间，另一人回到人群；经过
次选四人组，可在669个房间中各安排三人可交流；剩下六人由引理2可分住两个房间，每个房间各三人可交流.
练习册系列答案
相关题目
