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

Let the universal set be $S = \{1, 2, \dots, n\}$ with $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$.

We can analyze the connectivity of the vertices based on their subset sizes:

1. The Empty Set ($\{ \}$): Since the empty set has size $0$, its intersection with any other subset has size $0$. Thus, it has no neighbors and forms $1$ isolated component.
2. Singleton Sets ($\{i\}$): For any singleton set, its intersection with any other subset can have a size of at most $1$. Thus, none of the $n$ singletons can have an intersection of size $2$ with any set. Each singleton forms an isolated vertex, giving $n$ isolated components.
3. Subsets of size $\geq 2$: All remaining subsets of size $2$ or greater form a single connected component.
   To see this, any subset $A$ of size $\geq 2$ contains at least one pair of elements, say $\{a, b\} \subseteq A$. Since $|A \cap \{a, b\}| = 2$, $A$ is adjacent to the size-2 vertex $\{a, b\}$. Furthermore, any two size-2 vertices $\{a, b\}$ and $\{c, d\}$ can be connected via an intermediate vertex of size $4$ (for example, $\{a, b, c, d\}$ if they are disjoint, which is always possible since $n \geq 6$). Thus, all subsets of size $\geq 2$ are mutually reachable.

Summing these up, the total number of connected components in $G$ is: