GATE CSE 2006 | Question: 72

Question

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:

• A. $\binom{\frac{n}{2}}{2}.2^{\frac{n}{2}}$
• B. $2^{n-2}$
• C. $2^{n-3}\times 3$
• D. $2^{n-1}$

Comments

great   thanks!!

---

Watch from 00:43:00 to 01:33:54

https://www.youtube.com/watch?v=gTz15iPSXus&t=1757s

Deepak sir explained very well!

---

$\color{red}{\text{Detailed Video Solution,}}$ with Complete Analysis: https://youtu.be/O09byrun2JQ 

The above video solution covers complete analysis of the following 3 GATE questions:

https://gateoverflow.in/1850/gate-cse-2006-question-71 

https://gateoverflow.in/43566/gate-cse-2006-question-72 

https://gateoverflow.in/43567/gate-cse-2006-question-73 

Answer 1

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

Let $S = \{a_{1}, a_{2}, a_{3}, \dots, a_{n}\}$ be the given set of size $n$ and the vertex $v$ having the maximum degree contains $k$ elements, $\{a_{1}, a_{2}, a_{3}, \dots, a_{k}\}$.

As per the given condition, vertex $v$ can have edges to all vertices having EXACTLY two common elements. So, we can choose the $2$ elements from the vertex $v$ in ${}^kC_{2}$ ways, and, for each of these $2$ elements pair, say $\{a_{i}, a_{j}\}$, vertex $v$ can have an edge to all vertices which are subset of $(S – v), \cup \{a_{i}, a_{j}\} \; \because \text{First we find the subsets of S-v, and then put elments } a_i \text{ and } a_j \text{ into it}$.

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

Comments

awesome explanation sir :)

---

@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.035 times 2^n is the maximum we can get

No other answer can yield you this value.

Answer 2

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.

Comments

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?

Answer 3

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 ^kC₂ 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−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

^kC².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).

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

Comments

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

---

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

Answer 4

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