The 2n vertices of a graph G corresponds to all subsets of a set of size n,…

Conclusion: there are n + 1 vertices of degree zero.

• If a subset has size 0 or 1 (the empty set or any singleton), then no other subset can intersect it in exactly two elements, so those vertices have degree zero. There is 1 empty set plus n singletons, giving 1 + n such vertices.

• If a subset has size at least 2, then there exists some other subset whose intersection with it is exactly two elements, so such vertices do not have degree zero. Specifically:

  • If the subset is the whole n-element set, pick any 2-element subset; their intersection has size 2.

  • If the subset has size k with 2 ≤ k ≤ n−1, choose any two elements from the subset and (if needed) include at least one element outside the subset to form a different subset; this new subset will intersect the original in exactly those two elements.