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

Let $S$ be the set of size $n$, so that the vertices of the graph $G$ correspond to the $2^n$ subsets of $S$.

Let $A$ be a vertex corresponding to a subset of size $k$ (where $0 \le k \le n$). A vertex $B$ is adjacent to $A$ if and only if $|A \cap B| = 2$. To construct such a subset $B$:

1. We must choose exactly $2$ elements from $A$ to be in $B$. There are $\binom{k}{2}$ ways to do this.
2. For the remaining $n - k$ elements in $S \setminus A$, each element can either be included in $B$ or not. There are $2^{n-k}$ ways to make this choice.

Thus, the degree of a vertex corresponding to a subset of size $k$ is given by:

Let us evaluate $d(k)$ for different values of $k$ to find the maximum degree:

• For $k = 2$: $$d(2) = \binom{2}{2} 2^{n-2} = 1 \times 2^{n-2} = 2 \times 2^{n-3}$$
• For $k = 3$: $$d(3) = \binom{3}{2} 2^{n-3} = 3 \times 2^{n-3}$$
• For $k = 4$: $$d(4) = \binom{4}{2} 2^{n-4} = 6 \times 2^{n-4} = 3 \times 2^{n-3}$$
• For $k = 5$: $$d(5) = \binom{5}{2} 2^{n-5} = 10 \times 2^{n-5} = 2.5 \times 2^{n-3}$$

For any $k \ge 4$, the ratio of consecutive terms is:

Since $k \ge 3$, we have $2(k-1) > k+1$, which means the sequence $d(k)$ strictly decreases for $k \ge 4$.

Thus, the maximum degree is achieved at $k = 3$ and $k = 4$, and its value is:

Therefore, the correct option is C.