in Graph Theory edited by
13,775 views
73 votes
73 votes

The $2^n$  vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 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:

  1. $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$
  2. $2^{n-2}$
  3. $2^{n-3}\times 3$
  4. $2^{n-1}$
in Graph Theory edited by
13.8k views

3 Comments

25
25
Thanks.
0
0
great   thanks!!
0
0

5 Answers

70 votes
70 votes
Best answer

(C) $\max_k ({}^kC_2\times 2^{n-k}) = {}^3C_2 \times 2^{n-3} = 3\times 2^{n-3}$.

Let the vertex having the max degree contain $k$ elements. Now, as per the given condition, it can have edges to all vertices having two common elements (exactly $2$ common). So, we can choose the $2$ common elements in ${}^kC_2$ ways. Now, for each of these $2$ pair of elements, it can have an edge to a vertex containing $n-k$ elements $+$ the $2$ common elements. This will be equal to $2^{n-k}$ possible subsets as the $2$ common elements must always be present and other $k$ elements must always be absent. So, we get the degree as ${}^kC_2 \times 2^{n-k}.$

Now, our answer will be the maximum value for this. We can differentiate this (w.r.t k) and equate to $0$. But in other way we can try different values for $k$ starting with $2$. As we see if we increase $k$ from $2$ on wards, the $2^{n-k}$ term gets divided by $2$. The other term is ${}^kC_2$, which goes like $1, 3, 6, 10, \dots$ for $k = 2, 3, 4, 5, \dots$. So, we get the max. degree for $k = 3$ or $4$ and this will be $3 \times 2^{n-3}$.

edited by

4 Comments

awesome explanation sir :)
0
0

@Prateek Arora@Dheeraj Pant@rahul sharma 5 Look at the table in @Warrior's answer below. He has also calculated the values of degrees for the vertices according to the solution. But when you count the sum of degrees of all the vertices in the "Graph"(Question has mentioned that it is a graph) with n = 6 or 7 then it is not an "Even" value and it violates "Handshaking Theorem". What I figured out is that the correct solution considers that there are self loops For Eg. vertex {1,2} will be adjacent to vertex {1,2} , but it does not consider the fact that a self loop contributes degree 2 to a vertex. Did anyone think about this?

0
0
0.035 times 2^n is the maximum we can get

No other answer can yield you this value.
0
0
17 votes
17 votes
Let the set be S ={1,2,3,...n}

Consider a subset containing 2 elements of the form {1,2}. Now {1,2} will be adjacent to any 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 #ways of making such sets containing 1 and 2 is 2^n-2.

Hence, vertices with 2 elements will have 2^n-2 degree.

 

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

 

Hence, total no of subsets with 2 elements common with {1,2,3} is 3C2*2^n-3

Similarly, for 4 elements subset degree would be 4C2*2^n-4 and for 5 element subset 5C2*2^n-5 and so on.

We observe maximum value is obtained for 3 element or 4 element subset both of which have degree 3*2^n-3.

1 comment

Hi,


Here it is mentioned that any element can either be selected or not selected, if not selected then the set say {1,2} will have no other elements i.e only '1,2' will be there this leads to self loops right. Should we consider self loops as well?
1
1
15 votes
15 votes

For such problems, we need to check what is the pattern by taking extreme values.

Let n=4 elements which is repn by a set  S= {a,b,c,d} .

So G =< P(s) , E> where  P(s) represent the vertices of G and E is the set of edges of G.

Vertices of G = P(s) = {ϕ,{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}{a,b,c},{b,c,d},{a,b,d},{a,c,d},{a,b,c,d}} .

Total no of vertices = 2^4 =16

Edges of G = Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

Degree of Vertices D(v) of G

D(ϕ) = D({a})=D({b})=D({c}),=D({d}) = Degree of a vertex of G which having 0 or 1 element = 0

D({a,b})=D({a,c})=D({a,d})=D({b,c})=D({b,d})=D({c,d}) = Degree of a vertex of G which having 2 elements = 4 (with self loop) ,

See the Vertex {a,b} is incident with  {a,b} ,{a,b,c}, {a,b,d}, {a,b,c,d} so the degree of Vertex {a,b} is 4.

D({a,b,c})=D({a,c,d})=D({a,b,d})=D({b,c,d}) = Degree of a vertex of G which having 3 elements = 6,

See the Vertex {a,b,c} is incident with {a,b},{a,c},{b,c} ,{a,b,d} ,{a,c,d}, {b,c,d} so the degree of Vertex {a,b,c} is 6.

D({a,b,c,d})=  Degree of a vertex of G which having 4 elements = 6,

See the Vertex {a,b,c,d} is incident with {a,b},{a,c},{b,c} ,{b,d} ,{a,d}, {c,d} so the degree of Vertex {a,b,c,d} is 6.

When we increase the n values we see that the vertex of G which has 3 or 4 elements have the max Degree.

Generalization: Let the vertex of G which having k elements. Now, as per the given condition, it can have edges to all vertices having two common elements (exactly 2 commons).  So, we can choose the 2 common elements in kCways. Now, for each of these 2 pair of elements, it can have an edge to a vertex containing n−k elements + the 2 common elements. This will be equal to 2n−kpossible subsets as the 2 common elements must always be present and other k elements must always be absent. So, we get the degree as

kC2.2n−k

See the table for clear understanding,

Vertex of G having k elements of n Degree of Vertex of G having k elements of n Degree at n=6 ,n=7,n=8
k=0 ,vertex ϕ 0 0,0,0
k=1 0 0,0,0
k=2 C(2,2).2(n-2) =2(n-2) 16,32,64
k=3 C(3,2).2(n-3) = 3.2(n-3) 24,48,96
k=4 C(4,2).2(n-4) = 3.2(n-3) 24,48,96
k=5 C(5,2).2(n-5) = 10.2(n-5) 20,40,80
k=k C(k,2).2(n-k)  C(k,2).2(n-k) put n
k=n C(n,2).2(n-n) = C(n,2) 15,21,28

We can clearly see that Degree of Vertex of G having k =3 or k=4 elements of n having the max value which is 3.2(n-3).

The correct answer is (c)2(n-3)⨉3

2 Comments

@Warrior Thanku for such a wonderful explanation. . !!
1
1

@Warrior Add the degrees of the vertices for n = 6 or 7 then you will get "Odd" value..It violates Handshaking theorem.

0
0
4 votes
4 votes

c option should be the answer but I tried to explain this question to make myself and others understandable 

Answer:

Related questions