Prove that intersection of at least a pair of 3-member sets of {1, 2, …, n} is equal to one.

Question

Suppose we have $n+1$ subsets with $3$ members from the set of numbers from $1$ to $n$. I wanna prove that the intersection of two of these subsets, is exactly one member.

My idea is to decompose subsets into $n$ sets named $a[1], a[2], …, a[n]$ which each pair of sets in $a[i]$ have exactly $1$ member in common. Now, by the pigeonhole principle, we can prove the statement.

My other idea is to convert this problem to a graph. Graph $G$ has 2 parts $X$ and $Y$. Part $X$ consists of $n+1$ sets and part $Y$ consists of $n$ numbers (1 to n). Now, I draw an edge from each vertex in part $X$ to its members in part $Y$. So, we have to prove that there exists a pair of vertices $u, v\in X$ that the number of neighbors of $u$ and $v$ ($| N(u) \cap N(v)|$) is equal to one.

Thanks in advance for your help!

Answer 1

Here is an outline of a proof that seems to work (but there might be more elegant solutions).

1. Notation. Write $[n] = \{1,\ldots,n\}$, and let $\mathcal P([n]) = \{S : S \subseteq [n]\}$ be its power set. I will occasionally refer to the elements of $[n]$ as symbols.

2. Situation. Let $\mathcal S \subseteq \mathcal P([n])$ be a collection of $3$-element sets such that $|T_1 \cap T_2| \neq 1$ for all $T_1,T_2 \in \mathcal S$.

3. Definition. Let $\mathcal S$ be as in Situation 2. Define $G_{\mathcal S} = (V,E)$ to be the graph given by $V = \mathcal S$ and $E = \{\{T_1,T_2\} : T_1 \cap T_2 \neq \varnothing\}$. In other words, $V$ has a vertex for every $3$-element set in $\mathcal S$, and two sets/vertices $T_1,T_2 \in \mathcal S$ are connected if $T_1$ and $T_2$ intersect. (Note: if $T_1$ and $T_2$ are adjacent in $G_{\mathcal S}$, then $|T_1 \cap T_2| = 2$.)

4. Claim. If $\mathcal S$ is as in Situation 2, then $G_{\mathcal S}$ is a disjoint union of cliques.

Proof. Let $T_1T_2\cdots T_k$ be a path in $G_{\mathcal S}$ with $T_1 \neq T_k$. Then $|T_1 \cap T_k|$ is either $0$ or $2$.

Suppose $|T_1 \cap T_k| = 0$. Let $i$ be the least index such that $|T_i \cap T_k| \neq 0$. Then $|T_i \cap T_k| \geq 2$, by the assumption on $\mathcal S$ (cf. Situation 2). But $T_i$ contains only one element (i.e. symbol) which is not contained in $T_{i-1}$, so we also have $|T_{i-1} \cap T_k| > 0$: a contradiction. We conclude that $|T_1 \cap T_k| = 2$, so $T_1$ and $T_k$ are connected by an edge. $\quad\Box$

5. Claim. The only possible cliques in $G_{\mathcal S}$ are of the form $\{\{a,b,c_1\},\{a,b,c_2\},\{a,b,c_3\},\ldots\}$, or a subset of $\{\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\}\}$.

Proof. Suppose that $\mathcal C \subseteq \mathcal S$ is a clique in $G_{\mathcal S}$. Choose two subsets $T_1,T_2 \in \mathcal C$, which are necessarily of the form $T_1 = \{a,b,c\}$ and $T_2 = \{a,b,d\}$. Let $T_3 \in \mathcal C$ be distinct from $T_1$ and $T_2$. We distinguish two cases.

• If $T_3$ contains both $a$ and $b$, then we claim that $\mathcal C$ is of the form $\{\{a,b,c_1\},\{a,b,c_2\},\{a,b,c_3\},\ldots\}$. Indeed, write $T_3 = \{a,b,e\}$, and let $T_k \in \mathcal C$ be different from $T_1$, $T_2$, and $T_3$. If $T_k$ does not contain $a$, then $|T_1 \cap T_k| = 2$ forces $b,c \in T_k$; $|T_2 \cap T_k| = 2$ forces $b,d \in T_k$; and $|T_3 \cap T_k| = 2$ forces $b,e \in T_k$. But now $|T_k| \geq 4$, which is a contradiction. Analogously, $T_k$ must contain $b$, so every $T_k \in \mathcal C$ contains $a$ and $b$.

• If $T_3$ does not contain both $a$ and $b$, then $|T_1 \cap T_3| = |T_2 \cap T_3| = 2$ forces $T_3 = \{a,c,d\}$ or $T_3 = \{b,c,d\}$. By rearranging $a$ and $b$, we may assume without loss of generality that $T_3 = \{a,c,d\}$. Let $T_k \in \mathcal C$ be different from $T_1$, $T_2$, and $T_3$. Then $$ |T_k \cap \{a,b,c\}| = |T_k \cap \{a,b,d\}| = |T_k \cap \{a,c,d\}| = 2, $$ so the only remaining possibility is $T_k = \{b,c,d\}$. $\quad\Box$

6. Proposition. If $\mathcal S$ is as in Situation 2, then $|\mathcal S| \leq n$.

Proof. For every clique $\mathcal C$ in $G_{\mathcal S}$ one has $|\mathcal C| \leq \big|\bigcup_{T\in\mathcal C} T\big|$, by Claim 5. (In words: every clique uses at least as many symbols $a,b,c,\ldots \in [n]$ as it has vertices.) Since $G_{\mathcal S}$ is a disjoint union of cliques, and since different cliques use different symbols, it follows that $|\mathcal S| \leq n$. $\quad\Box$