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 4 of 4: Prove c(A) remains equal to k after the Step 3 transfers

Previous step Next step

In plain words

Everyone in $A$ (both $A \cap M$ and the people moved in Step 3) is friends with all of $B \cap M$ , so any clique $Q \subseteq A$ can be joined with $B \cap M$ to form a clique no larger than the global maximum $|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

Detailed analysis

In the final Room $A$ , $A \cap M$ is a clique of size $k$ , so $c(A) \ge k$ . For any clique $Q \subseteq A$ , every member is either in $A \cap M$ or was moved in Step 3, and in either case is friends with all of $B \cap M$ . Thus $Q \cup (B \cap M)$ is a clique. By maximality of $M$ , $|M| \ge |Q \cup (B \cap M)| = |Q| + |B \cap M| = |Q| + |M| - |A \cap M|$ , so $|Q| \le |A \cap M| = k$ . Hence $c(A) = k = c(B)$ .