# Distinct sets proof

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.
• 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. I did not get that ? Please explain a bit more. Thanks ! – Debashish Mar 24 '18 at 21:47
• @Debashish Each time you traverse an edge, the set changes at one point. And the change is at a different point every time: that's because each $x\in[n]$ corresponds to just one edge of the graph, and the trail does not use any edge more than once. So the changes can't be canceled out, they just accumulate. – bof Mar 24 '18 at 22:13
• @Debashish In other words, suppose each edge $e_x$ is labelled $x.$ Then, if there is a path $P$ from $A_i$ to $A_j,$ the symmetric difference $A_i\triangle A_j$ is just the set of labels occurring on the edges of $P.$ This is because each label is applied to at most one edge. – bof Mar 24 '18 at 22:24
• @Debashish Suppose, e.g., that there is a cycle $A_1A_2A_3A_4A_5A_1.$ Then there is an element $x\in A_1\triangle A_2.$ Let's say that $x\in A_1$ but $x\notin A_2.$ Then $x\notin A_3$ because $A_2\triangle A_3=\{y\}$ for some $y\ne x.$ For the same reason, $x\notin A_4,$ and $x\notin A_5,$ and $x\notin A_1.$ But now we have arrived at a contradiction, $x\in A_1$ and $x\notin A_1.$ – bof Mar 24 '18 at 22:49
• @Debashish In other words, if we follow a trail $v_0,v_1,v_2,\dots,$ then $$1=|v_0\triangle v_1|\lt|v_0\triangle v_2|\lt|v_0\triangle v_3|\lt|v_0\triangle v_4|\lt\cdots.$$ If we had $v_n=v_0$ (making a cycle), then we would have $|v_0\triangle v_0|=|v_0\triangle v_n|\gt0$ which is absurd. – bof Mar 24 '18 at 22:58