GATE CSE 2006 | Question: 73

Question

The $2^n$  vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$.  Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of connected components in $G$ is:

• A. $n$
• B. $n + 2$
• C. $2^{\frac{n}{2}}$
• D. $\frac{2^{n}}{n}$

Comments

@Bikram sir 

can you please explain the question with example... i am not able to understand these type of questions. :(

---

1. gate2006-71
2. after $1.$ Start solving this one. (73)
3. gate2006-72

Otherwise: Complete package  $\checkmark$

---

$\color{red}{\text{Detailed Video Solution,}}$ with Complete Analysis: https://youtu.be/O09byrun2JQ 

The above video solution covers complete analysis of the following 3 GATE questions:

https://gateoverflow.in/1850/gate-cse-2006-question-71 

https://gateoverflow.in/43566/gate-cse-2006-question-72 

https://gateoverflow.in/43567/gate-cse-2006-question-73 

Answer 1

Answer is Option B. 

Here’s how:-

Let $n = 6$, so the set is {$1$,$2$,$3$,$4$,$5$,$6$}. Now we all know what are the $2^n, i.e. 2^6$ subsets of it. 

Now, the question asks us to find the number of components in the graph. Here it’s said, “Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements.”

If we carefully see, the subset $\phi$ can’t intersect with any other subset, that too with 2 elements. But we know Null Graph is a connected graph. So it will form a single component.

Again if we observe the singleton subsets : {$1$}, {$2$}, ...{$6$}. These also can’t intersect with any subset and produce $2$ elements, because they themselves are of single element set. And even single node is a connected graph. So all these 6 subsets will be 6 different components. Here in the q it is the value 'n’.

Now we don’t need to worry about other subsets of $size>=2$ as all of them can intersect with others producing exactly $2$ elements. So all of these rest elements will form one single component.

Thus we have a total of : 1 [due to $\phi$] + n [single ton sets] + 1 [all subsets of $size>=2$] =  $n+2$

Answer 2

Answer will be n+2 because $\phi$ and $\{ 1\} \{ 2\} \{ 3\} \{ 4\}......\{ n\}$ will have degree 0 and all the other will be connected into one component.

so n+2 is the answer

Answer 3

Clearly $\phi$ and all the single size subsets({1}, {2},….,{n}) will be isolated vertices in the graph because they don’t even have two elements so how can their intersection with some other vertex will give two. So they all will form one component each. From here we get n+1 components.

Now if we form all subsets size two then none of them will be adjacent to each other as they cannot have both element same. If both element are same then subset itself is same. So there will be no edge between any pair of size 2 subsets.

It is given that n>=6 so now consider subsets of size four. Since any subsets of size two for eg. {1,2} and {3,4} cannot be adjacent to each other but we can make a subset of size 4 containing all those four element, i.e {1,2,3,4}. Now {1,2} and {3,4} may not be adjacent, but {1,2} is adjacent to {1,2,3,4} and {3,4} is also adjacent to {1,2,3,4} and this will be true for any pair of subset of size two we take. For eg: we can do this for {3,4} and {5,6} and by making them connected through {3,4,5,6}. So from this we get that take any two subsets of size two they will have a path between them.

Now if we consider any subset of size of size>2 then they all will be connected to at least one the subset of size two. For eg {1,2,3} will be connected to {1,2}, {2,3} and {1,3}. So all the subsets of size two have path between them and moreover all the subsets of size>2 will be connected to some subsets of size 2. Hence they all will form one component.

So total number of components = n+2.

Answer 4

Option B is Corrcect Answer .