第3题

在一场数学竞赛中，有些参赛者彼此是朋友。朋友关系总是相互的。若一个参赛者群体中的任意两人都是朋友，则称该群体为团。（特别地，少于两名参赛者的任意群体都是团。）团中成员的数目称为其大小。已知在这场竞赛中，团的最大大小为偶数，证明可以把参赛者安排到两个房间，使一个房间内所含团的最大大小等于另一个房间内所含团的最大大小。

第 2/4 步：处理 B cap M 中某个 x 不属于 B 的一个 (k+1)-团的情形

上一步下一步

通俗地说

将 $x$ 移回 $A$ 后，团 $A \cap M$ 扩大为大小 $k+1$ ，而 $C \subseteq B \setminus \{x\}$ 保持完整，因此 $c(B)$ 仍为 $k+1$ 。

\\exists\\, x \\in B \\cap M,\\ C \\subseteq B \\text{ clique with } |C| = k+1,\\ x \\notin C \\implies c(A \\cup \\{x\\}) = c(B \\setminus \\{x\\}) = k+1

详细分析

假设存在 $x \in B \cap M$ 以及一个大小为 $k+1$ 的团 $C \subseteq B$ ，满足 $x \notin C$ 。把 $x$ 从 $B$ 移回 $A$ ：此时 $A$ 含有 $M$ 的 $k+1$ 名成员，故 $c(A) = k+1$ ；而 $C \subseteq B \setminus \{x\}$ 仍有大小 $k+1$ （且 $c(B)$ 不会超过 $k+1$ ），所以 $c(B) = k+1 = c(A)$ ，证明结束。