retagged by
17,042 views
65 votes
65 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$
retagged by

4 Answers

Best answer
62 votes
62 votes

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

edited by
63 votes
63 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
13 votes
13 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 ?
1 votes
1 votes
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
Answer:

Related questions

43 votes
43 votes
8 answers
2
51 votes
51 votes
5 answers
4
gatecse asked Sep 21, 2014
11,368 views
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with ...