Register

GATE CSE 2006 | Question: 72

• edited by
17,780 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
User Avatar

6 Answers

0 votes
0 votes
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.
User Avatar
0 votes
0 votes
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) ]
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

65 votes
65 votes
4 answers
5
Rucha Shelke asked Sep 26, 2014
17,257 views
GATE CSE 2006 | Question: 71
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 number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
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 set...
User Avatar
43 votes
43 votes
8 answers
6
go_editor asked Apr 24, 2016
8,724 views
GATE CSE 2006 | Question: 73
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 number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
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 set...
User Avatar
51 votes
51 votes
5 answers
8
gatecse asked Sep 21, 2014
11,507 views
GATE CSE 2010 | Question: 1
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 $\xi(S) = \xi(T)$, then $| S| = 2| T |$ $| S | = | T | - 1$ $| S| = | T | $ $| S | = | T| + 1$
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 ...
User Avatar
Link Copied!