How do I find maximum degree of a vertex in $G$? Common Data for Questions $1, 2, 3:$
The $2^n$  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.
Q.1. The number of vertices of degree zero in $G$ is:

*

*$1$

*$n$

*$n + 1$

*$2^n$

Q.2.The maximum degree of a vertex in $G$ is:

*

*$^{n/2}C_2.2^{n/2}$

*$2^{n−2}$

*$2^{n−3}×3$

*$2^{n−1}$

Q.3. The number of connected components in $G$ is:

*

*$n$

*$n+2$

*$2^{n/2}$

*$\frac{2^n}{n}$

My Try:
Given there set size is $n$ where $n\geq6$. Number of vertices is $2^n$ of graph $G$.
Note that power of $n$ elements, i.e. $2^n$ elements in powerset of $n$ elements where $1$-element of size is $0$ i.e $\phi$.
$n$-element of size is $1$ i.e $\{1\} ,\{2\} ,\{3\},....,\{n\}$.
Similarly size of $k$, total number of elements are $^nC_k$.
Now,
Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements.
Note that $1$-element of size is $0$ i.e $\phi$ and
$n$-element of size is $1$ i.e $\{1\} ,\{2\} ,\{3\},....,\{n\}$ have less than two elements that can not be connected to any other vertices due to less number of elements in that sets, Total such element are$ = 1 + n$ and remaining (i.e. $2^n - (n+1)$) are connected, since these have more than one elements in that sets.
So, total number of connected components in $G$ is$ = (n+1)$ disconnected $+1$((i.e. $2^n - (n+1)$)remaining  are connected)$ = n + 2$.

I'm not getting Q.2.

Can you explain little bit please, how do I find maximum degree of a vertex in $G$?

Somewhere, it explained and answer is given $(^kC_2.2^{(n-k)}) =  ^3C_2 . 2^{(n-3)} = 3.2^{(n-3)}$.

Hint: 
you can compute the degree of a vertex of size $m$ as follow:


*

*first choose 2 elements among the $m$ to be the one that will make the conection

*then choose elements to complete the sets that you will be connected to. you can complete the sets with any number of elements from the $n-m$ elements left.


Once you get the formula for the degree of a vertex of size $m$ you have to find the maximum. I would proceed by derivation (I didn't do it but I think it would give you the expected result). Note that there may be a cleverer  way to get the maximum ...
I hope it helps
