Multiple choice

The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n $\ge$ 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. 2n
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

The vertices of degree zero will be those subsets which do not have two elements common with any other subsets. This is true only for the subsets of cardinality 0 and 1. Number of sets with cardinality 1 = n $\therefore$Number of vertices of degree 0 = n + 1

Keep practicing — related questions