Question

【题目】个人在某个节日期间互通电话问候，已知其中每个人至多打通了三个朋友家的电话，任何两个人之间至多进行一次通话，且任何三个人中至少有两人，其中一个人打通了另一个人家里的电话，求的最大值.

Answer 1

【答案】

【解析】

先证明引理.

引理 阶简单图中不存在，则.

其中，表示的边数.

引理的证明：设是各项顶点中度最大的顶点，设与相邻的点的集合为，

与不相邻的点的集合为 ，由于中无三角形，从而，在中没有边，则的其他边都在中或之间，这样的边都是由顶点引出的.

于是，

，

又，所以，.

下面证明原题.

用个点表示个人，如果一个人打通了另一个人家里的电话，则连一条从到的有向边，得到一个简单的有向图.

一方面，中无三角形，由引理有，

故，

另一方面，.

所以， ， ①

当为奇数时，式①变为，解得；

当为偶数时，式①变为，解得.

综上所述，.

最后，是可能的，构造两个,对其中每个七边形，令指向，则构图合乎条件，

首先，每个点作为始点都恰引出3条有向边，从而，每个人至多打通了3个朋友家的电话.

其次，对任何三个点，由抽屉原理知，必有两个点，在同一个中，若，则打通了家中的电话，若则打通了家中的电话.