in Graph Theory edited by
6,071 views
38 votes
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:

  1. $n$
  2. $n + 2$
  3. $2^{\frac{n}{2}}$
  4. $\frac{2^{n}}{n}$
in Graph Theory edited by
6.1k views

4 Comments

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

@Bikram sir 

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

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

Otherwise: Complete package  $\checkmark$

5
5

6 Answers

53 votes
53 votes
Best answer

(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

4 Comments

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

@Shaik Masthan

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

0
0
Probably my answer will give a clear explanation to this question
0
0
25 votes
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
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
7 votes
7 votes

Answer  (B) n + 2

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

Answer:

Related questions