Consider $n$ distinct sets , $A_1,A_2,A_3...A_n$ on $[n]$. Prove that there is an $x\in[n]$ such that $A_i - \{x\}$ are all distinct.
Construct a graph with nodes as the sets $A_i$ and edges between those sets, which differs by one element only.Edge labels are the separating elements. Now, to satisfy our requirement we must not have $n$ distinct labels. If the graph does not contain a cycle, then we are ok and statement holds. But if the graph contains a cycle then we have to manipulate the graph a bit.
Now if we somehow prove that in every cycle, each edge label occurs even number of times then we can do the manipulation as follows: keep one copy of each edge and delete other copies of that edge. In this way, we construct a new graph which can not have any cycle. So, we can have at max n - 1 distinct edge labels in this new graph and these are the original distinct labels in the original graph also.
But how to prove the assumed property of the cycle?
Thanks !
Let me write $A\triangle B$ for the symmetric difference $(A\setminus B)\cup(B\setminus A).$
Consider a graph $G$ which has $n$ nodes $A_1,A_2,\dots,A_n$ and at most $n$ edges chosen in the following way: For each $x\in[n],$ if there exist sets $A_i,A_j$ with $A_i\triangle A_j=\{x\},$ we choose one such pair of sets and draw the edge $e_x=A_iA_j.$
Note that, if there is a trail (no repeated edges) of length $k$ from $A_i$ to $A_j,$ then, since each $x\in[n]$ is added or subtracted at most once, we must have $|A_i\triangle A_j|=k.$ Therefore, the graph $G$ is acyclic. Therefore, it has at most $n-1$ edges. Therefore, there is at least one $x\in[n]$ such that $A_i\triangle A_j\ne\{x\}$ for all $i,j.$ Since the sets $A_1,A_2,\dots,A_n$ are distinct, it follows that the sets $A_1\setminus\{x\},A_2\setminus\{x\},\dots A_n\setminus\{x\}$ are also distinct.