edited by
6,237 views
47 votes
47 votes
Let $S$ be a set of $n$ elements $\left\{1, 2,\ldots, n\right\}$ and $G$ a graph with $2^{n}$ vertices, each vertex corresponding to a distinct subset of $S$. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly $2$ elements. Note: The symmetric difference of two sets $R_{1}$ and  $R_{2}$ is defined as $\left ({R_{1}}\setminus{R_{2}} \right)$ $\cup $ $\left ({R_{2}}\setminus{R_{1}} \right)$

Every vertex in $G$ has the same degree. What is the degree of a vertex in $G$?

How many connected components does $G$ have?
edited by

6 Answers

3 votes
3 votes

 


First part


Let us assume we are working with two set $A$ and $B$ and we shall work gradually on all possible sizes of set $A$. We work the cases by finding for a given cardinality of $A$, the possible sets $B$ such that

$|A\oplus B| = 2$, where $\oplus$ is the symmetric difference operator. In other words we need to have $|A\cup B|=|A\cap B| +2 \tag 1$

CASE 1: When $|A|=0$ i.e $A=\phi$

then, $|A\cap B|=0$ and we need to choose two elements from $n$ elements to form set $B$, such that $(1)$ is satisfied. [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $2$]

So number possible $B$’s = $^n C_2 = \frac{n.(n-1)}{2}$

CASE 2: When $|A|=1$ ; $A=\{ a\}$ $(say)$

(a) when $A\cap B=\phi$ then we should have only $1$ element in $B$ other than what is in $A$ and this can be done in $n-1$ ways. [vertex corresponding to set is $A$ is adjacent to all vertices which correspond to all other sets of size $1$]

(b) when $A \cap B=A$ then we should have in $B$ elements in $A$ and apart from that $2$ other elements than those in $A$. So the no. of possible $B$’s are $^{n-1}C_2=\frac{(n-1)(n-2)}{2}$ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets containing $a$ of size $3$]

So total number of possible $B$'s $= (n-1)+\frac{(n-1)(n-2)}{2} = \frac{n(n-1)}{2}$

CASE 3: When $|A|=2$, $A=\{a,b\}$ $(say)$

(a) when $A\cap B=\phi$ this as per the question would mean that $B=\phi$ and there is only $1$ possible choice. [vertex corresponding to set is $A$ is adjacent to vertices which correspond to the null set].

(b) when $|A\cap B|=1$, then we can choose in $^2C_1$ the element of $A$ to be present in $A\cap B$ and the remaining $1$ element of $B$ should be chosen as $^{(n-2)}C_1$. So the number of possible $B$’s = $^2C_1 . ^{(n-2)}C_1 = 2.(n-2)$ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $2$ containing either $a$ or $b$ but not both].

(c) when $|A\cap B|=2$ then we can choose in $^2C_2$ the element of $A$ to be present in $A\cap B$ and the remaining $2$ element of $B$ should be chosen as $^{(n-2)}C_2$. So the number of possible $B$’s = $^2C_2 . ^{(n-2)}C_2 = \frac{(n-2)(n-3)}{2}$. [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $4$ containing both $a$ and $b$].

So total number of possible $B$'s = $1+2.(n-2)+ \frac{(n-2)(n-3)}{2}=\frac{n(n-1)}{2}$

CASE 4: When $|A|=x$, where $x\geq 3$

(a) when $|A\cap B|=x-2$ then we can choose in $^xC_{x-2}$ ways the element of $A$ to be present in $A\cap B$ and the remaining $0$ elements of $B$ should be chosen as $^{(n-x)}C_0$. So the number of possible $B$’s = $^xC_{x-2} . ^{(n-x)}C_0 = \frac{x.(x-1)}{2}$ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $x-2$ containing any $x-2$ elements of $A$]

(b) when $|A\cap B|=x-1$ then we can choose in $^xC_{x-1}$ ways the element of $A$ to be present in $A\cap B$ and the remaining $1$ element of $B$ should be chosen as $^{(n-x)}C_1$. So the number of possible $B$’s = $^xC_{x-1} . ^{(n-x)}C_1 = x.(n-x)$. [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $x$ containing any $x-1$ elements of $A$].

(c)when $|A\cap B|=x$ then we can choose in $^xC_{x}$ ways the element of $A$ to be present in $A\cap B$ and the remaining $2$ elements of $B$ should be chosen as $^{(n-x)}C_2$. So the number of possible $B$’s = $^xC_{x} . ^{(n-x)}C_2 = \frac{(n-x).(n-x-1)}{2}$. [ [vertex corresponding to set is $A$ is adjacent to all vertices which corresponds to sets of size $x+2$ containing the $x$ elements of $A$].

So total number of possible $B$'s = $ \frac{x.(x-1)}{2}+ x.(n-x)+\frac{(n-x).(n-x-1)}{2}=\frac{n(n-1)}{2}$

So degree of each vertex is $\frac{n(n-1)}{2}$.


Second Part


From the discussion above, we can see that all the sets of even cardinality are in a component and all the sets of odd cardinality is in another component. So there are just $2$ components in the graph.

1 votes
1 votes
given :- Every vertex in G has the same degree.

Best way to solve is by seeing the degree of phi; which is nC2.

and for connected components take .Small example for n=2 and n=3 and draw u will get answer.

Related questions

60 votes
60 votes
6 answers
1
Kathleen asked Sep 14, 2014
13,377 views
Let $P(S)$ denotes the power set of set $S.$ Which of the following is always true?$P(P(S)) = P(S)$$P(S) ∩ P(P(S)) = \{ Ø \}$$P(S) ∩ S = P(S)$$S ∉ P(S)$
37 votes
37 votes
4 answers
3
Kathleen asked Sep 14, 2014
7,593 views
A polynomial $p(x)$ satisfies the following:$p(1) = p(3) = p(5) = 1$ $p(2) = p(4) = -1$The minimum degree of such a polynomial is$1$$2$$3$$4$
28 votes
28 votes
3 answers
4
Kathleen asked Sep 14, 2014
4,070 views
Let $S= \{0, 1, 2, 3, 4, 5, 6, 7\}$ and $⊗$ denote multiplication modulo $8,$ that is, $x ⊗ y= (xy) \mod 8$Prove that $( \{ 0, 1\}, ⊗)$ is not a group.Write three d...