edited by
8,580 views
43 votes
43 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:

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

8 Answers

Best answer
54 votes
54 votes

(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

edited by
27 votes
27 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 ...

16 votes
16 votes

Answer  (B) n + 2

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

11 votes
11 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
Answer:

Related questions

65 votes
65 votes
4 answers
2
37 votes
37 votes
7 answers
3
Ishrat Jahan asked Oct 31, 2014
8,727 views
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is aHamiltonian cyclegri...