Explanation

Dark Mode

13,775 views

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:

- $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$
- $2^{n-2}$
- $2^{n-3}\times 3$
- $2^{n-1}$

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}$.

@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

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.

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.

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 ^{k}C_{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

^{k}C^{2}.2^{n−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)}.**

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

0