# Induced subgraph of subset graph?

For a natural number $N$ we can construct a graph $\underline{\text{SubsetGraph}}(N)$ with vertices for each subset of $\{1,2,\ldots,N\}$ and an edge between two vertices when the corresponding subsets are disjoint.

Is it true that given any simple undirected graph $G$ with N vertices, it is a induced subgraph of $\underline{\text{SubsetGraph}}(N)$. How can you prove or disprove it ?

Edit:

I was wrong and @RGB was right, it's not easy to fix. Actually, this fact is not true.

A counterexample is as follows:

$\hspace{50pt}$

Suppose there exists a mapping $S : V \to \mathcal{P}(V)$ such that $(u,v) \in E$ if and only if $S_u \cap S_v = \varnothing$. We know that $(1,2) \in E$, so $S_1 \cap S_2 = \varnothing$ and WLOG we can assume that $|S_1| \leq 2$. However, $S_3$, $S_4$, $S_5$ are pairwise disjoint, and hence for $S_1$ to have non-empty intersection with each of them, we need $|S_3| \geq 3$, contradiction.

I hope this helps $\ddot\smile$

• I am getting sometimes two $S_v$ equal for different vertices. For example for the three vertex graph with edges $(ac),(bc)$. Don't we get $S_a=\{ab\}=S_b$?
– OR.
Jul 30, 2013 at 11:14
• I don't find it incredibly easy to fix. For example, every leaf of the graph is going to get the same $S$. If the number of leaves is large then how do you choose which elements to delete for which vertices? And not only for leaves, whenever a bunch of vertices do not have edges between them, this is going to happen. I have not idea how to fix it.
– OR.
Jul 30, 2013 at 12:00
• @RGB You are right, it's not easy to fix, it's not even true. You will find a counterexample and full explanation in the last edit. Jul 30, 2013 at 17:03