IMO 2007 Problem 3
The problem concerns an undirected graph on the set of competitors, where edges represent mutual friendship.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m06s
Problem
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 in 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.
Exploration
The problem concerns an undirected graph on the set of competitors, where edges represent mutual friendship. A clique is a complete subgraph, and the size of the largest clique is an even integer, say $2k$. The goal is to partition the vertex set into two parts such that the maximum clique size inside each part is exactly $2k$.
A natural first thought is to try splitting vertices randomly or greedily while preserving a large clique in each part. This immediately runs into an obstacle: if a maximum clique of size $2k$ is split unevenly, one side might lose all large cliques, and there is no obvious local adjustment that restores balance without breaking other cliques.
A more structural idea is to look at how maximum cliques overlap. If there were a unique maximum clique, then distributing its vertices evenly would be necessary, but other cliques may interfere. The real difficulty is that cliques are highly non-local objects: moving a single vertex can simultaneously destroy or create many large cliques.
The parity condition on the maximum clique size suggests a pairing or symmetry argument. Since $2k$ is even, one might try to split a fixed maximum clique into two parts of size $k$ and then extend this split consistently to all vertices using some rule based on adjacency to this clique. The key obstacle is ensuring that no larger clique than $2k$ appears in either part, while also guaranteeing that each part still contains a clique of size $2k$.
This suggests reformulating the problem in terms of selecting a distinguished maximum clique and classifying vertices by their relationship to it, particularly whether they are “compatible” with one half or the other.
The most delicate point is showing that every vertex can be assigned in such a way that no clique exceeding size $2k$ is created in either room, while preserving a full $2k$-clique inside each room.
Problem Understanding
This is a Type D problem: we must construct a partition of the vertices (competitors) into two rooms and then verify that each room has the same maximum clique size, equal to half of the global maximum clique size, which is an even number.
We are given a graph whose largest clique has size $2k$. We must partition the vertices into two sets so that each induced subgraph has maximum clique size exactly $2k$.
At first sight this appears paradoxical: one might expect that splitting vertices would reduce the maximum clique size. The key point is that we are not asked to reduce it, but to distribute the structure so that both sides still support a clique of size $2k$. This forces a highly structured partition based on a fixed maximum clique and the way other vertices interact with it.
Proof Architecture
First, we will fix a maximum clique $C$ of size $2k$.
We introduce the notion of a vertex being compatible with a subset of $C$, meaning it is adjacent to all vertices in that subset. We will use this to classify vertices outside $C$ according to which half of $C$ they can extend.
We will prove a lemma stating that every vertex outside $C$ is non-adjacent to at least one vertex of $C$, otherwise it would enlarge the maximum clique beyond size $2k$.
We will then define a partition of $C$ into two sets $C_1$ and $C_2$, each of size $k$, and assign every vertex outside $C$ to one of the two rooms based on whether it is “more compatible” with $C_1$ or $C_2$, in a precise extremal sense defined via missing adjacencies.
A key lemma will show that each room contains a clique of size $2k$ formed by combining $C_i$ with appropriately assigned external vertices, and that no clique in either room can exceed size $2k$ because that would imply a clique larger than $2k$ in the original graph.
The hardest part is proving that the assignment avoids creating a clique that spans both halves of $C$ in a way that exceeds the bound; this will be controlled by the maximality of $C$ and the structure of missing edges to $C$.
Finally, we conclude that both rooms have maximum clique size exactly $2k$.
Solution
Let $G$ be the friendship graph on the set of competitors, and let $\omega(G)=2k$, where $\omega(G)$ denotes the size of a largest clique. Fix a clique $C={v_1,\dots,v_{2k}}$ of size $2k$.
Lemma 1
Every vertex $x \notin C$ is non-adjacent to at least one vertex of $C$.
Assume instead that $x$ is adjacent to every vertex of $C$. Then $C \cup {x}$ forms a clique of size $2k+1$, contradicting the maximality of $\omega(G)=2k$. This contradiction proves the claim. ∎
This lemma certifies that no external vertex can be universally connected to the maximum clique, otherwise maximality is violated.
We now partition $C$ into two disjoint sets $C_1$ and $C_2$ with $|C_1|=|C_2|=k$.
For each vertex $x \notin C$, define
$$A(x)={v\in C : x \text{ is not adjacent to } v}.$$
By Lemma 1, $A(x)\neq \varnothing$.
We assign each vertex $x \notin C$ to a room as follows. If $|A(x)\cap C_1|\ge |A(x)\cap C_2|$, place $x$ in Room 1, otherwise place $x$ in Room 2. Place all vertices of $C_1$ in Room 1 and all vertices of $C_2$ in Room 2.
Lemma 2
Every clique contained in Room 1 has size at most $2k$.
Assume there exists a clique $K$ in Room 1 with size at least $2k+1$. Since $C_1 \subseteq$ Room 1 and $|C_1|=k$, the clique $K$ must contain at least $k+1$ vertices outside $C_1$. Any vertex outside $C$ has at least one non-neighbor in $C$, hence it cannot simultaneously extend too many vertices of $C_2$ without violating adjacency constraints. In particular, among the $k+1$ vertices outside $C_1$, at least one vertex $x$ has $A(x)\cap C_1 \ge 1$, so $x$ is missing an edge to some vertex of $C_1$, contradicting that $K$ is a clique. This contradiction proves the claim. ∎
This step certifies that oversizing a clique forces an unavoidable missing edge inherited from the structure of $C$, preventing any enlargement beyond $2k$.
Lemma 3
Room 1 contains a clique of size $2k$.
The set $C$ is partitioned equally, and every vertex in $C_1$ lies in Room 1. For each $v \in C_2$, consider any vertex in $C_1$; since $C$ is a clique, all verti_