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.

Dark Mode

6,071 views

38 votes

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:

- $n$
- $n + 2$
- $2^{\frac{n}{2}}$
- $\frac{2^{n}}{n}$

1

@Bikram sir

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

0

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

Otherwise: Complete package $\checkmark$

5

25 votes

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

10 votes

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

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