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

$\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 

---

Question if in future they ask: total number of edges in $G$
 

---

@DΛΞMON What the answer will be in that case?

2^n-n to (2^n-n)(2^n-n+1) /2  ?

Answer 1

(B) $n+1$ (subsets of size $< 2$ are all disconnected) $+1$ (subsets of size $\geq 2$ are all connected) $= n+2.$

https://math.stackexchange.com/questions/148305/is-a-single-node-graph-a-strongly-connected-component

Comments

@Shaik Masthan

Why is it taking value of $n\geq 6$? I mean why not $n\geq 3$

---

Probably my answer will give a clear explanation to this question

https://gateoverflow.in/43567/gate-cse-2006-question-73?show=379105#a379105

---

good hack @Vikrant Singh

Answer 2

Intersection of { } and any other subsets will never produce 2 elements as result is an empty set.So the node { } has a degree 0.Here we have 1 vertex whose degree is 0 as it is not connected to anyother elements and so we have 1 component.

Intersection of a set with single element and anyother set will never produce a result of set 2 because the result might produce a maximum of 1 element. So all sets with single elements (i.e) {1} , {2} , .... {n} will have a degree 0. . We have n vertices and each one of them has a degree 0 and so we have total of n components.

Now all elements of size 2 will be connected with {1,2,3,4...n}. All elements of set 3 will be connected with atleast one element of set 2 . EX: {1,2,3} intersection {1,2} will contain 2 elements. So set of size n and all sets of size 2 are connected and and each set of size 3 is connected with atleast one element of size 2. Similiarly every element of size 4 will be connected with atleast one element of size 4 and so on. Here we have only one component.

So we have a total of (n+2) components in our graph ...

Answer 3

Answer  (B) n + 2

I hope this diagram will give you an intuition about the connected components here.

Comments

great explanation ! eed more of this

Answer 4

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$

Comments

nice explaination

Answer 5

i m explaining it to make it little-bit easy.

with set size =n , no of subset =2^n

1.now [{}(null set also represent a vertex),{a}{b}{c}{d}{e}...........(also represent verteces as isolated veteces since they hav no common element )] , so, we have (n+1) verteces with 0 degree  

2. [{a,b}{b,c}{c,d}{d,e}{e,f}{f,g}{g,h}{h,i}...............] these subsets are common to any set whose cardinality is greater than 2 to make path between them, since all connected as network of branch they will be treated as 1 component

so, total component will be (n+1){with zero degree component} +1{all vertices as subsets connected whose cardinality >=2} = n+2

Answer 6

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