GATE CSE 2006 | Question: 71

Question

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 vertices of degree zero in $G$ is:

• A. $1$
• B. $n$
• C. $n + 1$
• D. $2^n$

Comments

Exam hack:

Given condition : Two vertices of GG are adjacent if and only if the corresponding sets intersect in exactly two elements.

Take an example A = {1,2,3,4,5,6}. Total subsets possible = 2^6 = 64.

Now we have degree 0 means nodes can be <=1 as with 1 node also no intersection possible.

• 0 node : only 1 subset possible {} ==>1
• 1 node : only 1 subset possible {1}, {2}, {3}, {4}, {5}, {6}. ==>n.          Hence , ans is 0 node + 1 node = n+1 option (C)

---

thanks bro

---

Read this explanation before looking at the answer

Each vertex of a graph is mapped to each subset of a set whose size is at least 6. (We can consider the vertices to be subsets) There is an edge between two vertices (or subsets ) only if the intersection of the two subsets results in 2 elements. eg {1,2} int {1,2,3}={1,2}, => there will be an edge. {1} int {1,2}={1}=>no edge.

---

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

Answer 1

Ans is (C).

no. of vertices with degree zero $=$ no. of subsets with size $\left(\leq 1\right)  = n+1$.

as edges are there for every vertex with two or more elements as we have a vertex for all subsets of $n$.

Comments

@arpit.bagri Each vertex of a graph is mapped to each subset of a set whose size is at least 6. There is an edge between two vertices (subsets) only if the intersection of the two subsets results in 2 elements. eg {1,2} int {1,2,3}={1,2}, => there will be an edge. {1} int {1,2}={1}=>no edge.

---

Nice explanation.

---

Where it is mentioned in question that there will be an edge between the vertices where the intersection result in two elements ? In question it is said the two vertices will be adjacent, does that mean there will be an edge between them ?

Answer 2

let n=6 which are {a,b,c,d,e,f}
2^n=2^6=64 vertices in graph G which all are subset of size 6 : {a,b,c,d,e,f}

Two vertices of G are adjacent if and only if they have exactly 2 elements
so vertex with size 1 : {a},{b},{c},{d},{e},{f}
and vertex with size 0 : { }
cant be adjacent to any vertex
HEnce, number of vertices of degree zero in G is: 6+1=7
in General , n+1

Ans is C

Comments

@Gate Ranker18

corresponding sets intersect in exactly two elements. 

What does "intersect" means here.

You only mention "they have exactly 2 elements" here.

---

It means if two sets has two common elements then only vertices which are representing these sets will be connected else they won't be connected.

---

ooopppp….nice explanation as compared to other answers

Answer 3

There is one-one correspondence here.

Given that each vertex in a graph G corresponds to subset of a set S (let) with n elements.
We know there are 2^n subsets, for the set S with size n. right.
So is the graph, ie it contains 2^n vertices.(Obvious)

We also know out of all subsets of set S, there are 'n' subsets with only one elements, right. ------ (note - 1)
And a subset with empty set.(phi) ----- (note - 2)

So they both cannot be adjacent to any other vertex, right.
So their degrees are zero  which means they are isolated vertices.

So there are n + 1 isolated vertices in the Graph with given condition (from note-1 and note-2) , right!
Hence n+1 vertices with degree 0

@arjun sir , is it a correct approach ?

Comments

Please tell me what is the meaning of "all subsets of a set of size n"?

I am taking it as, there are 2^n vertices and they are divided into subsets of size n each.

Answer 4

N = 6

Let's assume set be {a,b,c,d,e,f}

then vertex can be {a,b,c,d} and other set containing 4 elements

all the set containing 3 elements and so on.

there will be vertex containing ϕ, therefore, a degree of a vertex is 0

also, there are 'n' vertices that will contain only one element which does not have any adjacent vertex i.e. degree will be 0

therefore Number of Vertices of degree zero = n + 1

Comments

what is meaning of this line "Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements".

---

First you need to understand that we have a set S which contains n elements .

Second point is that the Graph G contains 2^n vertices . Now lets understand from where this number comes.

See we have to make all possible subsets of the given set S. There are in total 2^n subsets possible as to make a subset we can either choose an element or not choose that element.

Now v1 and v2 of graph will have an edge between them if subset 1 and subset 2 will have exactly 2 elements in common .

In general we can say that there is an edge between vi and vj if subset i and subset j have exactly two elements in common.

Hope this will help you