Graph and subset question . give a easy solution


#1

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.

The maximum degree of a vertex in G is:
(A) (n/2)C2 x 2^(n/2)
(B) 2^(n-2)
© 2^(n-3) x 3
(D) 2^(n-1)


#2

For maximum lets take one vertex is {1,2,3,4,5,6}

we can any one 2 vertices ,the vertex corresponds to that subset can be adjacent.
Total no of ways = n C2 = n (n -1)/2.

option a on solving gives = n^2(n - 2)/8

if you put n = 6 in all options we get 24,16,24,32 as answer ,and our answer 15.

Dat means we are wrong,

lets try we pick vertex = {1.2}

then intesection with set of 3 elements like {1,2,3} choose 1 out of 3,4,5,6 = 4 {1,2} is fixed.(4c1)
set of 4 elements like {1,2,3,4} choose 2 out of 3,4,5,6 = 4 {1,2} is fixed. = 6.(4c2)
set of 5 elements like {1,2,3,4,5} choose 3 out of 3,4,5,6 = 4 .(4c3)
set of 6 elements like {1,2,3,4,5,6} = 1
total = 13.

lets take
{1,2,3}
2 elements : 3 = n/2 c 2
3 elements: 3c1 * 3 = 9 = (n/2) c 1
4 elements : 3c2 * 3 = 9 = (n/2) c 2
5 elements: 3c3* 3 = 3 , =(n/2) c 3 = so total = 3 + 9 + 9 + 3 = 24.

so a and c can be options but a cant be ,there is no pattern like that.May be i can try with n = 7 ,with ne vertex = {1,2,3} ,so i will mark C.
somebody please find the sum of

n/2 c 2 + n/2 c 1 + n/2 c 2 + n/2 c 3 ??

Also questioner needs to edit subsets to 2^n nit 2n,this question has other linked questions:

The number of vertices of degree zero in G is??

The number of connected components in G is ??