Korean Mathematical Olympiad Final Round

Let $G$ be a graph on vertices $v_1, v_2, \dots, v_n$ such that two vertices $v_i$ and $v_j$ are adjacent if and only if $A_i \cap A_j \neq \emptyset$ and $i \neq j$. For a set $X$ of vertices of $G$, let $N(X)$ be the set of all vertices adjacent to every vertex in $X$.
Suppose, on the contrary, that $n \ge m + 2$, $m \ge 3$ and $|N(X)| = 1$ for all subsets $X \subseteq \{v_1, v_2, \dots, v_n\}$ with $|X| = m$.

Solution 1
A set of vertices is called a clique if every pair of vertices are adjacent in $G$. Let $T$ be a maximum clique of $G$. It is trivial that $|T| < m + 2$.

(1) We claim that $|T| = m + 1$. If not, let $T'$ be a set of $m$ vertices such that $T \subseteq T'$. Then $N(T') \neq \emptyset$ and therefore there is a vertex $v$ adjacent to all vertices in $T$. Then $T \cup \{v\}$ is a clique, contradictory to the assumption that $T$ is a maximum clique.

(2) No vertex $v \notin T$ has more than 1 neighbor in $T$. Otherwise, if $x, y \in T$ are adjacent to $v$, then $x, y \in N((T - \{x, y\}) \cup \{v\})$.

(3) Let $v \notin T$ and let $w_1, w_2 \in T$ be two vertices non-adjacent to $v$. Since $N((T - \{w_1, w_2\}) \cup \{v\})$ can not contain $w_1$ or $w_2$, it must contain $y \notin T$. Then $y$ is adjacent to at least $m - 1$ vertices of $T$, contradictory to (2) because $m \ge 3$. $\square$

Solution 2
Let $d_i$ be the degree of the vertex $v_i$. By considering the number of pairs $(X, y)$ of a set $X$ of $m$ vertices and a vertex $y$ adjacent to all vertices of $X$, we deduce
$$\sum_{i=1}^{n} \binom{d_i}{m} = \binom{n}{m}.$$

(1) If $d_i \le m$ for all $i$, then $\sum_{i=1}^n \binom{d_i}{m} \le n$ but $n < \binom{n}{m}$ because $3 \le m \le n - 2$. Therefore there exists $i$ such that $d_i \ge m + 1$. We may assume $d_1 \ge m + 1$.

(2) Let $S$ be the set of all neighbors of $v_1$. Then $|S| = d_1 \ge m + 1$. For a subset $X$ of $S$ with $|X| = m - 1$, since $|N(X \cup \{v_1\})| = 1$, there exists a unique vertex $a \in S - X$ such that $a$ is adjacent to all vertices of $X$.

If there are distinct subsets $X_1, X_2$ of $S$ each having $m-1$ vertices such that the corresponding vertices $a_1, a_2 \in S$ are identical, then $a_1(= a_2)$ is adjacent to all vertices in $X_1 \cup X_2$ and so a subset of $X_1 \cup X_2$ with $m$ vertices will have at least 2 common neighbors, contradictory to the assumption.

Therefore no two vertices $a \in S$ corresponding to some subset $X$ of $S$ with $m-1$ vertices can be identical and so $\binom{d_1}{m-1} \le d_1$. But this is a contradiction because $2 \le m-1 \le d_1 - 2$. $\square$

Solution 3
We use (1) of Proof 2 first to show that some vertex has degree at least $m + 1$.
We proceed by induction on $m$.
If $m=3$, then we use proof 1 to finish the proof.
If $m > 3$, then let $S$ be the neighbors of $v_1$. For every subset $X$ of $S$ with $m-1$ vertices, we have $|N(X \cup \{v_1\})| = 1$ and therefore the subgraph $G[S]$ induced on $S$ has the property that every set of $m-1$ vertices has exactly one common neighbor. Since $|S| \ge m + 1$, such a graph can not exist by the induction hypothesis. $\square$