in Graph Theory edited by
8,528 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}$
in Graph Theory edited by
8.5k views

4 Comments

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

7
7

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

1
1

8 Answers

54 votes
54 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

@Shaik Masthan

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

0
0
edited by
Probably my answer will give a clear explanation to this question

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

good hack @Vikrant Singh

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true