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 1 of 4: Initialize with a maximum clique M in Room A and migrate until c(A) <= c(B)

Previous step Next step

In plain words

Starting with all of $M$ in Room $A$ gives $c(A) = 2m \ge c(B)$ ; moving people one by one from $A$ to $B$ lowers $c(A)$ by $1$ and raises $c(B)$ by at most $1$ per step, so when $c(A) > c(B)$ first fails, $c(B)$ is either $k$ or $k+1$ , and $k \ge m$ because $M$ has even size $2m$ .

|M| = 2m, \\quad \\text{stop when } k = c(A) \\le c(B) \\le k+1, \\quad k = |A| = |A \\cap M| \\ge m

Illustrative K4 friendship graph: all four vertices form an even-sized maximum clique; it does not encode the room partition.

Detailed analysis

Let $c(X)$ denote the largest clique size in room $X$ . Fix a maximum clique $M$ of size $|M| = 2m$ , put $A = M$ and $B$ equal to all remaining competitors, so $c(A) = 2m \ge c(B)$ . While $c(A) > c(B)$ , move one person from $A$ to $B$ ; each move decreases $c(A) = |A|$ by $1$ and increases $c(B)$ by at most $1$ , so when the loop stops with $k = c(A) = |A| = |A \cap M|$ , we have $k \le c(B) \le k+1$ . Moreover $k \ge m$ : otherwise $|A \cap M| \le m-1$ and $|B \cap M| \ge m+1$ , which would give $c(B) - c(A) \ge (m+1) - (m-1) = 2$ , impossible since $c(B) \le c(A)+1$ at termination. If $c(B) = k$ we are already done; assume $c(B) = k+1$ henceforth (with $k \ge m \ge |B \cap M|$ ).