The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+33 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 vertices of degree zero in $G$ is:

  1. $1$
  2. $n$
  3. $n + 1$
  4. $2^n$
asked in Graph Theory by Active (3.7k points)
retagged by | 4.2k views

4 Answers

+36 votes
Best answer

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

answered by Boss (13.6k points)
edited by
Can you provide explanation for 72 ??
Can someone provide more explanation for 72 ?

akash try one time urself .

idea is make tree.from leaf to root.

at n level take one one element their is no two element common  u have n+1 set with different element. with one set phi also.

now at n-1 level make two element set  if u have one elemt common then u have max n-1 posibility so 2n-1. with common one element so total Nc1 2n-1. sets possible.

like for n-2 level make three element set  if u have two common then u have max n-2 posibility so 2n-2. with common one element so total Nc2 2n-2. sets possible.

now by doing this take degree when element have two common element.

at last u got c as ans. Upto n-3 elemnt degree increase then from n-1 level degree start decrease.

at level n-2 we will have subsets of size 3 ,and it can be adjacent to any of its subsets which will be of size 2 and are present at level n-1 , so total no of subsets are 2^n-2 and from this we subtract all the subsets of size 1 which are n-2 as well as phi , so now till what level will we keep repeating it ,like at level n-3 ,we will have subsets of size 4 and it can be adjacent to any of the node at level n-2 or n-1 , so how to proceed from here ?
Could some one pls explain the answer plz. I feel it very difficult to understand
$2^n$ vertices mean there is a vertex with no element. How is that possible?

Yes, vertex with 0 element is ϕ.

Let S is a set with n elements, S= {v1,v2,v3,,,,,,,,vn}

P(S) = { ϕ,{v1},{v2}...... {v1,v2,v3,,,,,,,,vn}} ,∣ P(S) ∣ = 2n

E = Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

So our desired graph will be G = <P(S), E> .

So vertices of G will be vertex with 0 element ( ϕ) ,vertex with 1 element(v1,v2, so on.

Oh yes, the $\phi$ set. I totally forgot. Thanks.
+25 votes
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
answered by Active (2.6k points)
But can you draw a graph with $\phi$ (no element) as vertex?
ϕ is just a vertex name like v1,v2 or a,b,c,d or anything else.
what does this statement mean ?

Two vertices are adjacent if and only if the corresponding sets intersect in exactly two elements
nice explanation! @gateRanker
nice explanation bro...thank you
+9 votes
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 ?
answered by Boss (22.6k points)
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.
+1 vote
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
answered by (333 points)
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

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
47,919 questions
52,324 answers
67,778 users