GATE CS 2006 Q71 — Graphs: Connectivity, Matching, Colouring

Let $S$ be the set of size $n$ (where $n \geq 6$). The vertices of the graph $G$ correspond to all $2^n$ subsets of $S$. Two vertices (subsets) $A$ and $B$ are adjacent if and only if $|A \cap B| = 2$.

A vertex $A$ has degree zero if there exists no other subset $B \subseteq S$ ($B \neq A$) such that $|A \cap B| = 2$. Let us analyze this based on the size of $A$, denoted by $k = |A|$:

• Case 1: $k = 0$ (the empty set $\emptyset$)
  For any subset $B$, $|\emptyset \cap B| = 0 \neq 2$. Thus, the empty set has degree $0$. There is $\binom{n}{0} = 1$ such vertex.
• Case 2: $k = 1$ (singletons)
  For any subset $B$, $|A \cap B| \leq |A| = 1 < 2$. Thus, no singleton set can have an intersection of size $2$ with any other set. All singletons have degree $0$. There are $\binom{n}{1} = n$ such vertices.
• Case 3: $k \geq 2$
  Since $|A| \geq 2$, we can always choose at least one pair of elements $\{x, y\} \subseteq A$.
  • If $k > 2$, the subset $B = \{x, y\}$ is distinct from $A$ and satisfies $|A \cap B| = 2$.
  • If $k = 2$, say $A = \{x, y\}$, any subset of the form $B = \{x, y\} \cup C$ (where $C \subseteq S \setminus A$ and $C \neq \emptyset$) satisfies $|A \cap B| = 2$. Since $n \geq 6$, the set $S \setminus A$ is non-empty, ensuring such a distinct $B$ always exists.
  Thus, no subset of size $k \geq 2$ has degree $0$.

Therefore, the total number of vertices of degree zero is $1 + n$.