The 2^n vertices of a graph G corresponds to all subsets of a set of size n, for n = 6. Two vertices of G are adjacent ...

Question

The 2^n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 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

Accepted Answer

n + 1  (Option C) Each vertex is a subset of an n-element set. Two subsets are joined only when they share exactly 2 elements. A vertex has degree zero when NO other subset can meet it in exactly two elements. A subset can never reach a 2-element overlap if it has fewer than 2 elements of its own. So count the subsets of size 0 and size 1.