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 maximum degree of a vertex in G is:
- A.
(n/2)C2 *2n/2
- B.
2n-2
- C.
2n-3 *3
- D.
2n-1
Attempted by 132 students.
Show answer & explanation
Correct answer: C
Key idea: count neighbours of a subset by fixing its size and using combinatorics.
Fix a vertex corresponding to a subset S of size k.
Any neighbour T must intersect S in exactly two elements. Choose which 2 elements of S are in the intersection: C(k,2) ways.
For the remaining n−k elements outside S, each may or may not be in T independently, giving 2^{n-k} choices.
Thus the degree of a vertex whose subset has size k is d(k) = C(k,2)·2^{n-k}.
Compare successive values: d(k+1)/d(k) = ((k+1)/(k-1))·1/2.
This ratio is >1 for k < 3 and <1 for k > 3, so d(k) increases up to k = 3 and then decreases. Therefore the maximum occurs at k = 3.
Evaluate at k = 3: d(3) = C(3,2)·2^{n-3} = 3·2^{n-3}.
Conclusion: The maximum degree of G is 3·2^{n-3}.