edited by
17,633 views
89 votes
89 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}$
edited by

6 Answers

Best answer
74 votes
74 votes

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

edited by
21 votes
21 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.
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

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

65 votes
65 votes
4 answers
1
43 votes
43 votes
8 answers
2
51 votes
51 votes
5 answers
4
gatecse asked Sep 21, 2014
11,366 views
Let $G=(V, E)$ be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in $G.$ If $S$ and $T$ are two different trees with ...