题目

在协会上有九个人,其中任意三个人总有两个相互认识.求证:其中总有四个人,他们相互认识.

提问时间：2021-01-20

答案

证:用平面上无三点共线的九个点A1,A2,A3,……,A9表示9个人,9点间两两相连,现对这些线段染色,若两人相互认识,则把对应两点间的连线染成红色,否则染成蓝色,得到二色完全图k9,现只需证明必存在红色k4.
由题设知二色完全图k9中无蓝色三角形.
现任取一点,由抽屉原理知,此点与另八点所连的8条线段中,至少有4条同色.
⑴若由任意点出发的8条线段中有4条蓝色线段,不妨设A1出发的四条线段A1A2,A1A3,A1A4,A1A5为蓝色,由于不存在蓝三角,故A2,A3,A4 ,A5组成的完全图k4为红色.
⑵若由任意一点出发的八条线段中至多有三条蓝色线段,即其中至少有5条线段为红色.又因为k9中红色线段边数不可能为9×5/2,所以从此点出发的八条线段中至少有6条是红色.不妨设A1出发的6条线段A1A2,A1A3,A1A4,A1A5,A1A6,A1A7为红色,考察此6点在,其组成的二色完全图比存在同色三角形,又由于不存在蓝三角形,所以同色三角必为红三角形,所以必存在红色完全图k4.
综上所述,其中总有4人,他们相互认识.