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

@JashanArora here graph has $2^{n}$ vertices not $n$..

---

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.

Answer 1

 

---

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 2

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.