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)}$.
 A: To find the vertices that a subset of size $k$ is connected to, you choose two of the elements to be the intersection, then can choose any of the $n-k$.  There are $k \choose 2$ ways to do the first and $2^{n-k}$ of the second.  As long as $k \gt 2$ this will not be the same subset.  You are trying to find the $k$ that maximizes the product. Adding one to $k$ will multiply the first term by $\frac {k+1}{k-1}$ and divide the second term by $2$, so you break even at $k=3$
Added:  The degree of a vertex is the number of other subsets that it intersects in exactly two elements.  For an example, let $k=5, n=12$.  The subset might as well be $\{1,2,3,4,5\}$ out of $\{1,2,3,4,5,6,7,8,9,10,11,12\}$.  How many other subsets intersect in exactly two elements?  We have to choose two elements for the intersection out of $\{1,2,3,4,5\}$, which we can do in ${5 \choose 2} = 10$ ways.  We can then have any or all of $\{6,7,8,9,10,11,12\}$, which has $2^7=128$ subsets.  In total, a five element subset has ${5 \choose 2}2^7=1280$ other subsets it is connected with.  Similarly, for $k \gt 2$, a $k$-element subset is connected to ${k \choose 2}2^{n-k}=\frac 12k(k-1)2^{n-k}$ other subsets.  For $k=2$, we have to subtract one because if the subset of the $n-2$ elements we pick is empty we have the same set as we started with.  We are asked to find the $k$ that maximizes this.  We find $$\begin {array} {c |c} k&\text {sets}\\ \hline2&2\cdot2^{n-2}-1\\3&3\cdot 2^{n-3}\\4&6\cdot 2^{n-4}\\5&10\cdot 2^{n-5} \end {array}$$ which is maximum at $k=3$ and $k=4$
A: 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
