I need to prove the following, using graph theory:
Let $S=\{1,2,...,n\}$, and $A_1,A_2,...,A_n$ different sub-sets of $S$ (but they don't have to be disjoint). Prove that there exists $x\in S$ such that the sets: $A_1\cup \{x\}, A_2\cup \{x\},...,A_n\cup \{x\}$ are different from each other.
Hint: Build a graph so that its vertices are $A_1,A_2,...,A_n$.
I tried using the hint, and I understood that somehow I need to define the edges between the vertices (for example, two vertices will be connected by an edge if and only if the two subsets are equal or maybe if they have only one different element between them, etc.), but I can't seem to gain any ground.. any help would be appreciated.
Thanks!
Here is a general idea of how I think this problem can be solved.
Build a digraph so that the vertices are $A_1,A_2....,A_n$ such that the edge from any vertex $A_i$ to $A_j$ means "$A_i$ is included in $A_j$"
Proof that it's impossible to have a loop of any size, because that would mean: "$A_i$ is included in $A_j$ and $A_j$ is included in $A_w$ and $A_w$ ... and $A_e$ is included in $A_i$" which is absurd, because it means $A_i$ is equal to $A_j$ and $A_w$ and $A_e$.
Then the graph has to have an element $A_x$ which it's out-degree is $0$.
Let $x \in A_x$ and $\forall i \in \{ 1,2,...,x-1,x+1,...n \}, x \notin A_i$ and make the graph such $A_1\cup \{x\}, A_2\cup \{x\},...,A_n\cup \{x\}$.
Look at that graph and proof there are no loops, and you should be there.