Prove that intersection of at least a pair of 3-member sets of {1, 2, ..., n} is equal to one. 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!
 A: 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$

A: There is a well-known problem (sometimes referred to as the "Oddtown" problem) generalizing this one: if you have a family of subsets of $\{1,2,\dots,n\}$ such that

*

*each subset has odd size, and

*any two subsets have even intersection,

then there can be at most $n$ of them. The proof is by linear algebra. Take $\mathbf x_1, \mathbf x_2, \dots \in \mathbb F_2^n$ to be the indicator vectors of these sets over $\mathbb F_2$. Then the first condition says that $\mathbf x_i \mathbin{\boldsymbol{\cdot}} \mathbf x_i = 1$ for all $i$, and the second condition says that $\mathbf x_i \mathbin{\boldsymbol{\cdot}} \mathbf x_j = 0$ for all $i \ne j$.
Then the vectors form an "orthonormal" basis of $\mathbb F_2^n$, where I put the word "orthonormal" in quotes because the usual dot product isn't an inner product here. Still, the proof that the vectors form a basis is the same as in $\mathbb R^n$, and means that there can be at most $n$ of them (the dimension of $\mathbb F_2^n$).

From here, it follows that if you have a family of $n+1$ subsets of $\{1,2,\dots,n\}$ such that every subset has size $3$, they can't all have even intersection. The only possible odd intersection is an intersection in only one element.
A: Let us write the $n$-element ground-set $S$ as $S=\{1,2,\ldots, n\}$ and let us write the $n+1$ sets as $x_1,x_2, \ldots, x_{n+1}$; then each $x_j$ is a 3-element subset of $S$. Furthermore, let us write $Y=\{x_1,x_2,\ldots, x_{n+1}\}$
Let $W$ be any subset of $Y$. Then we write as ${\cal{N}}(W)$ the integers $i \in S$
such that there is a $x \in S$ such that $i \in S$.
We make the following claims:

Claim 1: For any proper subset $U$ of $S$ there is at least one $x_j$ s.t. $1 \le |x_j \cap U| \le 2$, lest we are done.

Indeed, then there are $b$ elements $x$ of $Y$ s.t. $x \subseteq U$
and there are $n+1-b$ elements $x$ s.t. $x \subseteq S \setminus U$.
Writing $|U|=a$ with $a$ positive and less than $n$, if $a<b$ then we can finish using induction. If
$a \ge b$ then $|S \setminus U| = n-a < n+1-b$ so we can use induction here as well. $\surd$
Now let us fix a set $x_1 \in Y$. And let us write $x_1=\{1,2,3\}$. By Claim 1 we can order $Y$ s.t. there is some integer $j' \ge 2$ s.t. each of $x_2,\ldots x_{j'}$ intersects $x_1$, and $x_{j'+1}$ does not, if $j'$ satisfies $j'<n+1$ that is. Now, we may assume that each of $x_2,\ldots x_{j'}$ intersects $x_1$ at exactly 2 elements in the ground-set, lest we are done [$x_{j+1}$ and $x_{j+2}$ cannot share 3 elements lest they are the same set]. We make the following claim:

Claim 2: Let us use the notation in the above paragraph. Let $A_1$ be the set of $x_j$ that intersect $x_1$ at precisely $\{1,2\}$; $A_2$ be the set of $x_j$ that intersect $x_1$ at precisely $\{2,3\}$; and $A_3$ the set of $x_j$ that intersect $x_1$ at precisely $\{1,3\}$, and let us assume WLOG that $|A_1| \ge |A_2| \ge |A_3|$. Then by Claim 1, $A_1 \cup A_2 \cup A_3$ is nonempty. Also, lest we are done, if $A_2 \cup A_3$ is nonempty then $|A_1| = 1$, and so $|A_1 \cup A_2 \cup A_3| \le 3$.

Indeed, let us suppose that $x_2,x_3 \in A_1$. Then one can write $x_2=\{1,2,4\}$
and $x_3=\{1,2,5\}$. Then any $x \in A_2 \cup A_3$ will satisfy either
$|x \cap x_2|=1$, or $|x \cap x_3|=1$. And so Claim 2 follows. $\surd$

Claim 3: Let us assume that $|A_1 \cup A_2 \cup A_3| \le 3$. Then let
us define $U$ to be the following subset of $S$:
$$U=\{i: i \in x {\text{ for some }} x \in A_1 \cup A_2 \cup A_3 {\text{ or }} i=1,2,3\}.$$
Let $x_{j'+1} \in Y$ s.t. $1 \le |x_{j'+1} \cap W| \le 2$. Then:
(i) $U \le 6$ and so is a proper subset of $S$
(ii) $x_{j'+1}$ exists by Claim 1
(iii) $x_{j'+1}$ does not intersect $x_1=\{1,2,3\}$
(iv) $x_{j'+1}$ intersects at least one $x \in A_1 \cup A_2 \cup A_3$ at exactly one element in $S$ [because each $x \in A_1 \cup A_2 \cup A_3$ contains
exactly one element in $U \setminus \{1,2,3\}$].


Claim 4. Let us assume that $|A_1 \cup A_2 \cup A_3| \ge 4$.
Then as in Claim 3 let us write
$$U=\{i: i \in x {\text{ for some }} x \in A_1 \cup A_2 \cup A_3 {\text{ or }} i=1,2,3\}.$$
Then
(i) $A_2 \cup A_3$ is empty [by Claim 2]
(ii) $|A_1| \le n-3$
(iii) Each $x \in A_1$ is of the form $\{1,2,i\}$; $i \ge 4$.
(iv) Let $x'$ be any element in $Y \setminus A_1$ that also is not $x_1$.
[Such an $x'$ exists by (ii).] If $U$ is a proper subset of $S$ let us assume that
$1 \le |x \cap U| \le 2$ otherwise $x \subset U$. Then $|x' \cap x =1|$ for at least one $x \in A_1 \cup A_2 \cup A_3$.

We now show (iv). Let us write $x'=\{i_1,i_2,i_3\}$. Then each of $i_1,i_2,i_3 \ge 4$ because $x' \not = x_1$ and $x' \not \in A_1$ and so $x' \not \in A_1 \cup A_2 \cup A_3$ by (i).
However, by definition of $U$, there is an $x \in A_1$ such that $i_1 \in x$
and so by (iii) of the claim, $x=\{1,2,i\}$. So $|x' \cap x|=1$. $\surd$
Claims 3 and 4 exhaust the possibilities, so the result follows.
