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

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 

---

in this question n>=6 is given  for no reason take smaller n and solve

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

0.035 times 2^n is the maximum we can get

No other answer can yield you this value.

---

Good catch @Ashish Lakhmani. 

---

Based on the image you uploaded, here is the step-by-step differentiation and the solution to find the value of $k$.

We start with the equation given in your image:

$$\frac{d}{dk} \left( 2^{n-k} \cdot \left[ \frac{k(k-1)}{2} \right] \right) = 0$$

Step 1: Apply the Product Rule

Let's define the two parts of the product as functions of $k$:

• $u = 2^{n-k}$

• $v = \frac{k(k-1)}{2} = \frac{k^2 - k}{2}$

The product rule states that $(uv)' = u'v + uv'$. Let's find the derivatives of $u$ and $v$ with respect to $k$:

• Derivative of $u$: Using the chain rule, $\frac{d}{dk}(2^{n-k}) = 2^{n-k} \cdot \ln(2) \cdot (-1) = -2^{n-k}\ln(2)$

• Derivative of $v$: $\frac{d}{dk} \left( \frac{1}{2}(k^2 - k) \right) = \frac{1}{2}(2k - 1) = \frac{2k - 1}{2}$

Now, substitute these back into the product rule formula:

$$\left( -2^{n-k}\ln(2) \right) \cdot \left( \frac{k^2 - k}{2} \right) + \left( 2^{n-k} \right) \cdot \left( \frac{2k - 1}{2} \right) = 0$$

Step 2: Simplify the Equation

Factor out the common term, which is $\frac{2^{n-k}}{2}$:

$$\frac{2^{n-k}}{2} \left[ -\ln(2)(k^2 - k) + (2k - 1) \right] = 0$$

Since $2^{n-k}$ can never be equal to $0$ for any real numbers, we can safely divide both sides by $\frac{2^{n-k}}{2}$ to eliminate it:

$$-\ln(2)(k^2 - k) + (2k - 1) = 0$$

Expand and group the terms by powers of $k$:

$$-(\ln 2)k^2 + (\ln 2)k + 2k - 1 = 0$$

$$-(\ln 2)k^2 + (\ln 2 + 2)k - 1 = 0$$

Multiply the entire equation by $-1$ to make the leading coefficient positive (standard quadratic form $ak^2 + bk + c = 0$):

$$(\ln 2)k^2 - (\ln 2 + 2)k + 1 = 0$$

Step 3: Solve for $k$ using the Quadratic Formula

Here, our coefficients are:

• $a = \ln 2$

• $b = -(\ln 2 + 2)$

• $c = 1$

Plug these into the quadratic formula, $k = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$:

$$k = \frac{(\ln 2 + 2) \pm \sqrt{(-(\ln 2 + 2))^2 - 4(\ln 2)(1)}}{2 \ln 2}$$

Let's expand the part under the square root (the discriminant):

$$(\ln 2 + 2)^2 - 4\ln 2 = (\ln 2)^2 + 4\ln 2 + 4 - 4\ln 2$$

The $+4\ln 2$ and $-4\ln 2$ cancel out, leaving:

$$(\ln 2)^2 + 4$$

Final Answer

Substitute the simplified discriminant back into the formula to get the exact values for $k$:

$$k = \frac{\ln(2) + 2 \pm \sqrt{(\ln 2)^2 + 4}}{2 \ln(2)}$$

 

To find the decimal values for $k$, we can calculate the two possible outcomes from the quadratic formula:

$$k = \frac{\ln(2) + 2 \pm \sqrt{(\ln 2)^2 + 4}}{2 \ln(2)}$$

Using the approximate value of $\ln(2) \approx 0.693147$:

For the positive root (+):

$$k \approx \frac{0.693147 + 2 + \sqrt{(0.693147)^2 + 4}}{2 \times 0.693147}$$

$k \approx 3.46958$

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?

---

nice explaination

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.

---

A small question isn't it

the 2 elemennt vertice will connect to $2^{n-1} -1$ and not $2^{n-1}$ here is my logic

let $\{a, b\}$ is a 2 element vertices then it can connect to only its supersets(to have exactly 2 common) that are $2^{n-2}$ which includes $\{a, b\}$  itself so the degree of any 2 element vertice will be $2^{n-1} - 1$

 

similarily for

3 element vertice $\{a, b, c\}$, choose 2 elements out of 3 $3 \choose2$, then for each 2 elements we have $2^{n-3}$ supersets possible which includes $\{a, b, c\}$ so for it also ${3 \choose 2} * (2^{n-3} -1 )$

 

so a $k$ element verices will have degree ${k \choose 2} (2^{n-k} - 1)$ now just find the first derivative with repect to $k $

rewriting the equaition as, $ f(k) =\frac{k(k-1)}{2} * (2^{n-k} - 1)$

---

A Nice answer @RahulVerma3 ...! 
(probably a smalle typo in 2^(n-1) - 1 instead of 2^(n-2) - 1 ) in : "which includes {a , b} itself so the degree of any 2 element vertice will be 2^(n-1) - 1 "

Answer 4

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

Answer 5

Let us pick one random vertex of the graph and assume it is a subset S with size k.

According to the question another vertices would be “adjacent if and only if the corresponding sets intersect in exactly two elements”.

Degree of this vertex = Other subsets that has exactly 2 elements in common with S.

For number of adjacent vertices, first we pick 2 elements that are common in both = kC2

Now we cannot take any other element from the rest of the k-2 elements of S1 because then there will be three or more elements common, but we want exactly two.

There are n-k elements remaining, for each of them we can either leave it or take it,

degree(S, k) = (kC2) * 2⁽ⁿ ⁻ ᵏ⁾

Now we have to find the value of k for which  degree(S, k) will be maximum,

The maximum value of degree(S,k) = 3 * 2⁽ⁿ ⁻ ³⁾

[This value appears when k=3 and k=4, and it depends only on k as we can take  2ⁿ common from each term of degree(S,k) ]

Answer 6

If you generalise this question,

I have devised a formula

For intersection to be exactly k elements k<<n

 

Formula is

$(k+1)*2^{n-(k+1)}$

 

In our case it is (k=2)

$3*2^{n-3}$

 

For k=3 it is

$4\times 2^{n-4}$ and so on

You can verify this.

Comments

Derivation?