有 $n$ 位游客，其中任意 $3$ 人中必有 $2$ 人互相不认识，并且把这 $n$ 个人任意分为两组来坐公交车，至少有一辆车上有互相认识的人，证明：存在一位游客，他至多认识 $\dfrac{2}{5}n$ 位游客．
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
用 $n$ 个点表示 $n$ 位游客，若两人互相认识，则对应两点连一条边，否则不连边，得到一个图．由已知条件知图中不存在三角形，并且不是二部图．由结论可知必含奇圈，设为中长度最短的奇圈．由于图中不存在三角形，故奇圈的长度是最短的假设知不在圈上的每个顶点没有连边（否则存在更短的奇圈）．故这个奇圈上每个顶点的度数之和，即存在一位游客，他至多认识其他 $\dfrac{2}{5}n$ 位游客．
答案
解析
备注
