Question

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 - 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 - 2 which must be highest.
Please suggest suitable approach to it.

Comments

i also got ur ans in first attempt but its seems incorrect bcoz if n will be large enough then given ans will be larger and correct and it is not like i m only mathing options u can see that after taking 3 element u r getting that ans .

Answer 1

Your solution seems correct. But

"intersection has two common elements"

Is it exactly two or at least two?

Comments

it should be exactly