656 views
Let $S$ be a set of $n$ elements $\left\{1, 2,....., n\right\}$ and $G$ a graph with 2$^{n}$ vertices, each vertex corresponding to a distinct subset of $S$. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly $2$ elements. Note: The symmetric difference of two sets $R_{1}$ and  $R_{2}$ is defined as $\left ({R_{1}}\setminus{R_{2}} \right)$ $\cup$ $\left ({R_{2}}\setminus{R_{1}} \right)$

Every vertex in $G$ has the same degree. What is the degree of a vertex in $G$?

How many connected components does $G$ have?
edited | 656 views
Good question.

$S = {1,2,3,4,5,6.....n}$

Let us assume any two subset $S_1$ and $S_2$. We can simply assume $n(S_1 \cap S_2) =0$ to consider the disconnected sets if we want.

Now there are three cases in which $(S_1 \backslash S_2) \cup (S_2 \backslash S_1) \;\; Or, \;\; (S_1 \oplus S_2)$ has only $2$ element.

1. Both green shaded area has one element each and in this case sizes of $S_1$ and $S_2$ are same.
2. The green area of $S_1$ contains $2$ element and the green area of $S_2$ contains none. In this case size of $S_1$ is $2$ more than that of $S_2$.
3. The green area of $S_2$ contains $2$ element and the green area of $S_1$ contains none. In this case size of $S_2$ is $2$ more than that of $S_1$.

So, if we are only interested in a particular set vertex corresponding to set $S_1$ of size $= m$, then $S_1$ is connected to three types of set vertices as shown below. We will use the words "set" and "vertices" synonymously.

In this above image, we have considered $m \geq 2$. The cases for $m = 1 \text{ and } m = 0$ will be discussed later.

Now, what we need to find is the no of set vertices in each of the above three types and sum them up to get the degree of the vertex corresponding to the set $S_1$.

For simplicity let us assume $S = \{1,2,3,4,5,6,7\}$ and set $S_1 = \{1,2,3,4\}$. Our interest will be to find $S_2$ such that vertices corresponding to $S_1$  and $S_2$ are connected.

1. CASE 1 : If we try to find another set $S_2$ having $4$ elements and satisfying constraint $n(S_1 \oplus S_2) = 2$, then we will see that no of such set $S_2$ is $4 \cdot (7 - 4)$. Or in general if $S_1$ is an $m$ element set then no of such $S_2$ sets with constraint $n(S_1 \oplus S_2) = 2$ will be equal to $m\cdot (n-m)$.
2. CASE 2 : $S_1$ contains $4$ element and If we try to find $S_2$ where $S_2$ contains $2$ elements and satisfying constraint $n(S_1 \oplus S_2) = 2$, then no of such $S_2$ will be $4C2$ or in general, for $m$ element set $S_1$, we have $mC2$ no of $S_2$ type sets all with $(m-2)$ size.
3. CASE 3: $S_1$ contains $4$ element and If we try to find $S_2$ where $S_2$ contains $6$ element and satisfying constraint $n(S_1 \oplus S_2) = 2$, then no of such $S_2$ sets will be $3C2$ or $(7-4)C2$. In general, with $S_1$ being $m$ element set, then $(n-m)C2$ no of $S_2$ sets will be possible.

Therefore, summing all three cases :

Degree of vertex $S_1$ ( assuming general case of $n(S_1) = m$ )

\begin{align*} &=m\cdot (n-m) + \binom{m}{2} + \binom{n-m}{2} \\ &=m\cdot n - m^2 + \frac{m^2}{2} - \frac{m}{2} + \frac{(n-m)\cdot (n-m-1)}{2} \\ &=m\cdot n - m^2 + \frac{m^2}{2} - \frac{m}{2} + \frac{n\cdot (n-1)}{2} \\ &\qquad - \frac{n \cdot m}{2} - \frac{n \cdot m}{2} + \frac{m^2}{2} + \frac{m}{2} \\ &=\frac{n\cdot (n-1)}{2} \\ &=\binom{n}{2} \\ \end{align*}

This result is independent of $m$ for $m \geq 2$ and $m \leq n$.

For $m = 0$ and $m = 1$ also we can show that degree of $0$ and $1$ size set vertices is nothing but $nC2$ only. (fairly straight forward cases).

So we can conclude that every vertex has the same degree and the degree is $nC2$.

Now we can guess one thing by looking at the following image:

i.e.for $m \geq 2$ if $m$ is even the $S_1$ is connected to only even cardinality type of sets (at least one) or if $m$ is odd then $S_1$ is connected to only odd cardinality type of sets (at least one). By this, we can almost say that there are two connected components in the graph.

But there is little more argument before we can proceed and have a valid proof.

if $m = 0$ then $S_1 = \phi$, Then $S_1$ will be connected to all $m = 2$ type of sets or $2$ cardinality sets.

if $m = 1$ then $S_1$ will be one of all $1$ element sets, Then $S_1$ will be connected to all other $1$ cardinality sets and at least one $3$ cardinality set.

We can argue that, one $m$ (even) cardinality set is at least connected to one $(m-2)$ cardinality set. That particular $(m-2)$ cardinality set is at least connected to one $(m-4)$ cardinality set and so on till $\phi$ set vertex. There for all even cardinality sets are connected to $\phi$ directly or indirectly.

A similar argument holds for odd cardinality set vertices till we reach some $1$ cardinality set. Moreover all $1$ cardinality sets are connected

Therefore we have a situation now that all even cardinality sets form one connected component and all odd cardinality set form another component.

For example : $n = 4$ :

answered by Veteran (56.9k points) 36 189 498
selected by
formula for symmetric difference is $\left ( R_{1}\cup R_{2} \right )-\left ( R_{1}\cap R_{2} \right )$, rt?
Yes. Both formulae are same.
but why u take $S=\left \{ 1,2,3,4,5,6,7 \right \}$

and $S_{1}=\left \{ 1,2,3,4 \right \}$

Is it set difference 2?

We only want to work with symmetric difference 2, rt?

I think two Edges  (i) 234 to 124  and (ii)123 to 134  are missing in your example  (n=4  ist component which is green).Though an amazing explanation for such Qs.Thanks.:)

@Debashish plz chk this line

Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements

then tell me just one thing how u r dividing set difference as m and (n-m) ?

how do we confirm that n elements set and (n-m) elements set has set diff exactly 2?

Thank You so much @Debashish Deka ji.

Best way to solve this for GATE is to take $n=2$ and $n=3$ and we get degree of each vertex = ${}^nC_2$ and no. of connected components = $2$.

Lets do it more formally.

It is clear {} should get connected to all $2$ element subsets (and not to any other) of $S$. So, degree of the corresponding vertex is ${}^nC_2$ as we have ${}^nC_2$ ways of choosing 2 elements from $n$. So, answer to first part must be this as it is given degree of all vertices are same.

Now, for the second part, from the definition of $G$ all the vertices of cardinality $k$ will be disconnected from all the vertices of cardinality $k-1$. This is because either all the $k-1$ elements must be same in both or $k-2$ elements must be same in both or else the symmetric difference will be more than $2$. Now if $k-1$ elements are same, symmetric difference will just be $1$. If $k-2$ elements are same, we have one element in one set not in other and $2$ elements in other set not in this, making symmetric difference $3$. Thus symmetric difference won't be $2$ for any vertices of adjacent cardinality  making them disconnected.

All the vertices of same cardinality will be connected - when just one element differs. Also, vertices with cardinality difference 2 will be connected- when 2 new elements are in one vertex. Thus we will be getting $2$ connected components in total.

.
answered by Veteran (319k points) 577 1442 2960
@arjun sir.. i am not being able to understand this. what is the better way to understand this? or which resourse i should refer to learn this question topic?
@sheshang you can read the answer given by Debashish . it is very clearly described.

set {1,2,3}

power set { {}, 1 ,2,3, {1,2}, {2,3} ,{1,3}, {1,2,3,} }

according to property above diagram is gnerated .

Now You can ans both the questions.

answered by Veteran (25.3k points) 13 60 192