The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
2.6k views

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}$
asked in Graph Theory by Veteran (103k points)
edited by | 2.6k views

4 Answers

+28 votes
Best answer

(C) $\max_k ({}^kC_2.2^{n-k}) = {}^3C_2 . 2^{n-3} = 3.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 . 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 . 2^{n-3}$.

answered by Boss (13.6k points)
edited by
0
vertex having the max degree contain k elements. ?  What do you mean by it ? Why exactly two common elements ?

Could some one provide more easy explanation to it ?
0
Very well explained!!!!
0
does the graph have self loop as well? because in 2^(n-k), we can have a combination of all 0s i.e. no element from n-k is also there.
0
Is self loop is considered??
0
Yes.Intesection of set with two elements with itself is 2 elements
0
the explanation is not very convincing
+32

the best explanation  of this question given by kiran sir

0

Though here $n\geq 6$ still take n= 3  S={1,2,3}

Here A is powerset of S and B is subset of A with 2 elements in common ... So the max degree according to formula will be 3 which is {1,2,3} ...  

Correct me if i am wrong ...

+1
nice explanation thanks sushmita for this great help
+1
No body can explain better then this
+10 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.
answered by Active (3.2k points)
+7 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

answered by Loyal (6.8k points)
+1
@Warrior Thanku for such a wonderful explanation. . !!
+3 votes

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

answered by Active (4.9k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,845 questions
47,507 answers
145,768 comments
62,262 users