The 2n vertices of a graph G corresponds to all subsets of a set of size n,…
2006
The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G is:
- A.
n
- B.
n+2
- C.
2n/2
- D.
2n / n
Attempted by 75 students.
Show answer & explanation
Correct answer: B
Answer: n+2
Reason:
Vertices corresponding to the empty set and to any singleton are isolated. They cannot have intersection of size 2 with any other subset, so each of these 1 + n vertices forms its own component.
Every subset of size at least 2 is adjacent to at least one 2-element subset contained in it: choose any two elements of the subset to get a 2-element subset whose intersection with the original subset is exactly those two elements.
All 2-element subsets lie in a single connected piece. For any two 2-element subsets P and Q, let S = P ∪ Q. If P and Q intersect, S has size 3 and is adjacent to both P and Q (intersection size 2). If P and Q are disjoint, S has size 4 and is adjacent to both. Since n ≥ 6 (so such unions are valid subsets), P and Q are connected through S. Thus every pair of 2-element subsets can be joined by a short path.
Combining these observations, every vertex of size at least 2 is connected (via a 2-element subset) to this unique large component containing all 2-element subsets. Therefore the vertices split into (1) the empty set, (2) the n singletons, and (3) one big component containing all other subsets.
Total number of connected components = 1 (empty set) + n (singletons) + 1 (big component) = n + 2.