第3题

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

第 4/4 步：证明第3步转移后 c(A) 仍等于 k

上一步下一步

通俗地说

$A$ 中的每个人（包括 $A \cap M$ 和第3步移入者）都与 $B \cap M$ 的所有成员是朋友，因此任意团 $Q \subseteq A$ 都能与 $B \cap M$ 合并成不超过全局最大值 $|M|$ 的团。

Q \\subseteq A \\text{ clique} \\implies Q \\cup (B \\cap M) \\text{ is a clique} \\implies |Q| + |B \\cap M| \\le |M| \\implies |Q| \\le |A \\cap M| = k

详细分析

最后的房间 $A$ 中， $A \cap M$ 是大小为 $k$ 的团，所以 $c(A) \ge k$ 。对任意团 $Q \subseteq A$ ，其每个成员要么在 $A \cap M$ 中，要么是在第3步移入的；两种情况下都与 $B \cap M$ 的所有成员为朋友。因此 $Q \cup (B \cap M)$ 是一个团。由 $M$ 的极大性， $|M| \ge |Q \cup (B \cap M)| = |Q| + |B \cap M| = |Q| + |M| - |A \cap M|$ ，故 $|Q| \le |A \cap M| = k$ 。于是 $c(A) = k = c(B)$ 。