Problem 3

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Step 3 of 4: When every (k+1)-clique of B contains B cap M, peel one non-M member per (k+1)-clique

Previous step Next step

In plain words

Because $|C| = k+1 > m \ge |B \cap M|$ , every $(k+1)$ -clique of $B$ must contain someone outside $M$ ; moving one such person to $A$ destroys $C$ while every moved person is friends with all of $B \cap M$ .

\\forall\\, C \\subseteq B \\text{ with } |C|=k+1:\\ B \\cap M \\subseteq C \\implies C \\setminus M \\ne \\emptyset

Detailed analysis

If Step 2 does not apply, every clique $C \subseteq B$ of size $k+1$ contains $B \cap M$ . Since $|C| = k+1 > m \ge |B \cap M|$ , $C \setminus M$ is non-empty. While $c(B) = k+1$ , choose such a $C$ and move one member of $C \setminus M$ from $B$ to $A$ ; each move lowers $c(B)$ by at most $1$ and leaves $B \cap M$ unchanged, so we stop with $c(B) = k$ . Every moved competitor belonged to a clique containing $B \cap M$ , hence is friends with all of $B \cap M$ .