Consider the following set : {1,2,3,.....n}. Now consider all possible subset. Two subset S1 and S2 are having edge between them only if their intersection has two common elements.
Find:
a) Number of isolated vertices.
b) Number of components
c) Highest degree possible.
Answers:
a) n+1
b) n+2
c) 3*2^{n-3}
I have problem in c) part answer.
My answer is 2^{n} - n - 2
My Approach:
I believe Highest degree should be of subset: {1,2,3....n} itself.
as it will be connected to every other vertices across.
It only not connected with single element set, phi and itself.
So its degree is 2^{n} - n - 2 which must be highest.
Please suggest suitable approach to it.