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 2 of 4: Handle the case where some x in B cap M misses a (k+1)-clique of B

Previous step Next step

In plain words

Moving $x$ back to $A$ enlarges the clique $A \cap M$ to size $k+1$ , while leaving the witnessing clique $C \subseteq B \setminus \{x\}$ intact so $c(B)$ stays $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

Detailed analysis

Suppose there exist $x \in B \cap M$ and a clique $C \subseteq B$ of size $k+1$ with $x \notin C$ . Move $x$ from $B$ back to $A$ : then $A$ consists of $k+1$ members of $M$ , so $c(A) = k+1$ , while $C \subseteq B \setminus \{x\}$ still has size $k+1$ (and $c(B)$ cannot exceed $k+1$ ), so $c(B) = k+1 = c(A)$ and we stop.