Let S be a set of n elements {1, 2, ..., n} and G a graph with 2^n vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding subsets has exactly 2 elements.
Note: The symmetric difference of two sets A_1 and A_2 is defined as (A_1 - A_2) ∪ (A_2 - A_1).
Every vertex in G has the same degree. How many connected components does G have?
GATE 2000 · Discrete Mathematics · Set Theory · medium
Answer: Every vertex has degree C(n,2) = n(n-1)/2; G has 2 connected components.
Compute the degree of a vertex A: The subsets B with |A △ B| = 2 are exactly the subsets obtained by choosing any 2-element subset T of S and setting B = A △ T. There are C(n,2) choices for T, each giving a distinct B. So deg(A) = C(n,2) = n(n-1)/2 for every vertex A.
Determine connected components via parity: Since each edge toggles exactly 2 elements, the parity of the subset size (even or odd) is preserved along every edge. The 2^(n-1) subsets of even cardinality form one component and the 2^(n-1) subsets of odd cardinality form the other (reachability within each parity class can be verified). Hence G has exactly 2 connected components.