6,071 views

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:

1. $n$
2. $n + 2$
3. $2^{\frac{n}{2}}$
4. $\frac{2^{n}}{n}$

A graph with 0 vertex is called a Null graph .

And a Null graph is connected graph .. If a graph is connected if any two vertices can be connected by a path, then the null graph is also connected.

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

(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

it is contributing in connected components n +1  vertices are disconnected and bigger block which connect remaining all so n+1+1  components

@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

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

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

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

1
13,767 views