GATE CSE 2000 | Question: 6

Question

Let $S$ be a set of $n$ elements $\left\{1, 2,\ldots, 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?

Comments

Can someone provide easy solution to this question?

---

Consider this, two vertices are adjacent iff the symmetric difference is 2 that is the number of elements not common=2, also the degree of all vertices are same which means the degree of phi is equal to degree of all the vertices and the degree of phi is equal to number of subsets with 2 elements hence nC2.

---

@Akshara Nair Wow that's very nice.. simple yet tricky

Answer 1

$S = {1,2,3,4,5,6,\ldots,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$ :

Comments

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.

---

they have mentioned every vertex has same degree..so if we consider empty set ..then it will be connected to nC2 (means n(n-1)/2) vertices as symmetric difference will be 2 with all of them, thereofore ans will be nC2

---

in general if S1 is an m element set then no of such S2 sets with constraint n(S1⊕S2)=2 will be equal to m⋅(n−m).

 in general, for m element set S1, we have mC2 no of S2 type sets all with (m−2) size.

sir how you got this.....?

---

@ajaysoni1924 in case 1) as we can see (m-1) elements will be common in both sets between S1 and S2 and size of both sets will also be same. .
Now we have to find number of such S2's , for that we will select (m-1) out of m elements (as any of (m-1) can be common) $\left(\begin{array}{c}m\\ m-1\end{array}\right)= m$ and now for the m th element we have (n-m) choices ..So its m(n-m) 

---

@Punit Sharma brother can you explain little bit more by an example, I am not getting this.

Edited

Got it thanks

---

thanku @dd for such a beautiful answer of this question

---

In the provided solution , for n = 4 won't the nodes {2,4} and {1,2,3} will be connected? And if it gets connceted, then there will only be one component. Am I missing something?

---

how their symm diff is 2? {1,3,4}

Answer 2

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.

.

Comments

@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.

Answer 3

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.

Comments

Hi,

Here using the diagram its easy to calculate for the 2 or 3 element set, but for higher order set how can we derive the degree of the vertices and number of connected components?

Answer 4

This question can be approached in following way too.

We know that we can represent subset $S_i$ of $S$ where $|S|=n$ using $n-length$ binary string $B_i$.

Where $B_i[j] = 1$ iff $j^{th}$ element of set $S$ does belong to $S_i$.

Now, Degree of a given vertex is just number of different $n-length$ binary string we can make using just toggling exactly 2 element from binary string corresponding to given vertex.

There are $n\choose2$ ways of selecting 2 bits which needs to be toggled so subsequently there are $n\choose2$ neighbours of given vertex.

Now for number of connected component note that parity of bit-string remains same after toggling(here togling means $0$ to $1$ or $1$ to $0$ no other action.) exactly 2 bits.

So odd-parity bit string forms 1 connected component and even-parity bit string forms 1 connected component so total 2 CC.

Comments

Amazing way to look at the question!!

---

The way you interpreted this question is very amazing. Thanks for explanation in simple and logical way. I just bypass this question by seeing the line "All vertices have same degree"  and just calculated number of neighbours of phi which is nc2 or two elements subsets. Thanks again for explaining.

Answer 5

 

---

First part

---

Let us assume we are working with two set $A$ and $B$ and we shall work gradually on all possible sizes of set $A$. We work the cases by finding for a given cardinality of $A$, the possible sets $B$ such that

$|A\oplus B| = 2$, where $\oplus$ is the symmetric difference operator. In other words we need to have $|A\cup B|=|A\cap B| +2 \tag 1$

CASE 1: When $|A|=0$ i.e $A=\phi$

then, $|A\cap B|=0$ and we need to choose two elements from $n$ elements to form set $B$, such that $(1)$ is satisfied. [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $2$]

So number possible $B$’s = $^n C_2 = \frac{n.(n-1)}{2}$

CASE 2: When $|A|=1$ ; $A=\{ a\}$ $(say)$

(a) when $A\cap B=\phi$ then we should have only $1$ element in $B$ other than what is in $A$ and this can be done in $n-1$ ways. [vertex corresponding to set is $A$ is adjacent to all vertices which correspond to all other sets of size $1$]

(b) when $A \cap B=A$ then we should have in $B$ elements in $A$ and apart from that $2$ other elements than those in $A$. So the no. of possible $B$’s are $^{n-1}C_2=\frac{(n-1)(n-2)}{2}$ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets containing $a$ of size $3$]

So total number of possible $B$'s $= (n-1)+\frac{(n-1)(n-2)}{2} = \frac{n(n-1)}{2}$

CASE 3: When $|A|=2$, $A=\{a,b\}$ $(say)$

(a) when $A\cap B=\phi$ this as per the question would mean that $B=\phi$ and there is only $1$ possible choice. [vertex corresponding to set is $A$ is adjacent to vertices which correspond to the null set].

(b) when $|A\cap B|=1$, then we can choose in $^2C_1$ the element of $A$ to be present in $A\cap B$ and the remaining $1$ element of $B$ should be chosen as $^{(n-2)}C_1$. So the number of possible $B$’s = $^2C_1 . ^{(n-2)}C_1 = 2.(n-2)$ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $2$ containing either $a$ or $b$ but not both].

(c) when $|A\cap B|=2$ then we can choose in $^2C_2$ the element of $A$ to be present in $A\cap B$ and the remaining $2$ element of $B$ should be chosen as $^{(n-2)}C_2$. So the number of possible $B$’s = $^2C_2 . ^{(n-2)}C_2 = \frac{(n-2)(n-3)}{2}$. [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $4$ containing both $a$ and $b$].

So total number of possible $B$'s = $1+2.(n-2)+ \frac{(n-2)(n-3)}{2}=\frac{n(n-1)}{2}$

CASE 4: When $|A|=x$, where $x\geq 3$

(a) when $|A\cap B|=x-2$ then we can choose in $^xC_{x-2}$ ways the element of $A$ to be present in $A\cap B$ and the remaining $0$ elements of $B$ should be chosen as $^{(n-x)}C_0$. So the number of possible $B$’s = $^xC_{x-2} . ^{(n-x)}C_0 = \frac{x.(x-1)}{2}$ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $x-2$ containing any $x-2$ elements of $A$]

(b) when $|A\cap B|=x-1$ then we can choose in $^xC_{x-1}$ ways the element of $A$ to be present in $A\cap B$ and the remaining $1$ element of $B$ should be chosen as $^{(n-x)}C_1$. So the number of possible $B$’s = $^xC_{x-1} . ^{(n-x)}C_1 = x.(n-x)$. [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $x$ containing any $x-1$ elements of $A$].

(c)when $|A\cap B|=x$ then we can choose in $^xC_{x}$ ways the element of $A$ to be present in $A\cap B$ and the remaining $2$ elements of $B$ should be chosen as $^{(n-x)}C_2$. So the number of possible $B$’s = $^xC_{x} . ^{(n-x)}C_2 = \frac{(n-x).(n-x-1)}{2}$. [ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $x+2$ containing the $x$ elements of $A$].

So total number of possible $B$'s = $ \frac{x.(x-1)}{2}+ x.(n-x)+\frac{(n-x).(n-x-1)}{2}=\frac{n(n-1)}{2}$

So degree of each vertex is $\frac{n(n-1)}{2}$.

---

Second Part

---

From the discussion above, we can see that all the sets of even cardinality are in a component and all the sets of odd cardinality is in another component. So there are just $2$ components in the graph.

Answer 6

given :- Every vertex in G has the same degree.

Best way to solve is by seeing the degree of phi; which is nC2.

and for connected components take .Small example for n=2 and n=3 and draw u will get answer.