Question

The $2^n$ vertices of graph G correspond to all subsets a set of size n, for $n\ge 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. $\left(\begin{array}{c}n/2\\ 2\end{array}\right)2^{n/2}$
• B. $2^{n-2}$
• C. $2^{n-3}\times 3$
• D. $2^{n-1}$

Answer 1

The correct option is C $2^{n-3}\times 3$

Let the set be S = {1, 2, 3, 4, ..., n}

Consider a subset containing 2 elements of the form {1, 2}. Now {1, 2} will be adjacent to an subset with which it has exactly 2 elements in common. These sets can be formed by adding zero or more elements from remaining n - 2 elements to the set {1, 2}. Since each of these elements may be either added or not added, number of way of making such sets containing 1 and 2 is $2^{n-1}$.

$\therefore$ Vertices with 2 elements will have $2^{n-2}$ degrees.

Now consider subsets of 3 elements say {1, 2, 3}. Since we want exactly 2 elements common, we choose these in ${}^3{C}_2$ ways and the we can add or not add remaining n-3 elements. This can be done in $2^{n-3}$ ways.

$\therefore$ Total number of subsets with at least 2 elements common with {1, 2, 3} is given by ${}^3{C}_2\times 2^{n-3}.$

Similarly, we can argue that the number of degrees of 4 element subsets is ${}^4{C}_2\times 2^{n-4}$ and from 5 element subsets is ${}^5{C}_2\times 2^{n-5}$ and so on.

Out of these $2^{n-2}={2.2}^{n-3}$ is less than ${}^3{C}_2\times 2^{n-1}=3\times 2^{n-3}.$

Then ${}^3{C}_2\times 2^{n-3}=3\times 2^{n-3}$ is same as ${}^4{C}_2\times 2^{n-4}=6\times 2^{n-4}=3\times 2^{n-3}\text{and}{}^4{C}_2\times 2^{n-4}=3\times 2^{n-3}$ is greater than ${}^5{C}_2\times 2^{n-5}=10\times 2^{n-5}=2.5\times 2^{n-3}$

$\therefore$ maximum degree in this graph is occurrence for 3 element and 4 element subsets both of which have $3\times 2^{n-3}$ degree.