The 2ⁿ vertices of a graph G corresponds to all subsets of 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 little observation of the adjacent vertices of different subsets reveals that the maximum degree will be possessed by a subset of size $\dfrac{n}{2}$. Suppose an example to compute the maximum degree. Set is {1,2,3,4,5,6} We have a subset of size $\dfrac{n}{2}${1,2,3} Now let us compute its degree The number of adjacent subsets of size 2 = ³C₂ = 3 For each one of {1,2} {2,3} and {1,3} There are 3 subsets of size 3 which are adjacent to {1,2, 3} e.g       {1,2,4}, {1,2,5}, {1,2,6} {2,3,4} {2,3,5} {2,3,6} In this way, for each of {1,2}, {2,3} and {1,3} there are ³C₂ subsets of size 5 for each of the three. The set itself would not be adjacent to {1,2,3} $\therefore$The maximum Degree = 3 + 3 x 3 + 3 x 3 + 3 = 24 $\therefore \binom{n/2}{2}2^{n/2}$= ³C₂ 2³ = 3 x 8 = 24