edited by
6,230 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

Best answer
52 votes
52 votes

$S = {1,2,3,4,5,6,\ldots,n}$

Let us assume any two subset $S_1$ and $S_2$. We can simply assume $n(S_1 \cap S_2) =0$ to consider the disconnected sets if we want. 

Now there are three cases in which $(S_1 \backslash S_2) \cup (S_2 \backslash S_1) \;\; Or, \;\; (S_1 \oplus S_2) $ has only $2$ element.

  1. Both green shaded area has one element each and in this case sizes of $S_1$ and $S_2$ are same.
  2. The green area of $S_1$ contains $2$ element and the green area of $S_2$ contains none. In this case size of $S_1$ is $2$ more than that of $S_2$.
  3. The green area of $S_2$ contains $2$ element and the green area of $S_1$ contains none. In this case size of $S_2$ is $2$ more than that of $S_1$.

So, if we are only interested in a particular set vertex corresponding to set $S_1$ of size $= m$, then $S_1$ is connected to three types of set vertices as shown below. We will use the words "set" and "vertices" synonymously. 

 

In this above image, we have considered $m \geq 2$. The cases for $m = 1 \text{ and } m = 0$ will be discussed later.

Now, what we need to find is the no of set vertices in each of the above three types and sum them up to get the degree of the vertex corresponding to the set $S_1$.

For simplicity let us assume $S = \{1,2,3,4,5,6,7\}$ and set $S_1 = \{1,2,3,4\}$. Our interest will be to find $S_2$ such that vertices corresponding to $S_1$  and $S_2$ are connected.

  1. CASE 1 : If we try to find another set $S_2$ having $4$ elements and satisfying constraint $n(S_1 \oplus S_2) = 2$, then we will see that no of such set $S_2$ is $4 \cdot (7 - 4)$. Or in general if $S_1$ is an $m$ element set then no of such $S_2$ sets with constraint $n(S_1 \oplus S_2) = 2$ will be equal to $m\cdot (n-m)$.
  2. CASE 2 : $S_1$ contains $4$ element and If we try to find $S_2$ where $S_2$ contains $2$ elements and satisfying constraint $n(S_1 \oplus S_2) = 2$, then no of such $S_2$ will be $4C2$ or in general, for $m$ element set $S_1$, we have $mC2$ no of $S_2$ type sets all with $(m-2)$ size.
  3. CASE 3: $S_1$ contains $4$ element and If we try to find $S_2$ where $S_2$ contains $6$ element and satisfying constraint $n(S_1 \oplus S_2) = 2$, then no of such $S_2$ sets will be $3C2$ or $(7-4)C2$. In general, with $S_1$ being $m$ element set, then $(n-m)C2$ no of $S_2$ sets will be possible.

Therefore, summing all three cases :

Degree of vertex $S_1$ ( assuming general case of $n(S_1) = m$ )

$\begin{align*} 
&=m\cdot (n-m) + \binom{m}{2} + \binom{n-m}{2} \\
&=m\cdot n - m^2 + \frac{m^2}{2} - \frac{m}{2} + \frac{(n-m)\cdot (n-m-1)}{2} \\
&=m\cdot n - m^2 + \frac{m^2}{2} - \frac{m}{2} + \frac{n\cdot (n-1)}{2} \\ 
&\qquad - \frac{n \cdot m}{2} - \frac{n \cdot m}{2} + \frac{m^2}{2} + \frac{m}{2}  \\
&=\frac{n\cdot (n-1)}{2} \\
&=\binom{n}{2} \\
\end{align*}$

This result is independent of $m$ for $m \geq 2$ and $m \leq n$.

For $m = 0$ and $m = 1$ also we can show that degree of $0$ and $1$ size set vertices is nothing but $nC2$ only. (fairly straight forward cases).

So we can conclude that every vertex has the same degree and the degree is $nC2$.


Now we can guess one thing by looking at the following image:

i.e.for $m \geq 2$ if $m$ is even the $S_1$ is connected to only even cardinality type of sets (at least one) or if $m$ is odd then $S_1$ is connected to only odd cardinality type of sets (at least one). By this, we can almost say that there are two connected components in the graph.

But there is little more argument before we can proceed and have a valid proof.

if $m = 0$ then $S_1 = \phi$, Then $S_1$ will be connected to all $m = 2$ type of sets or $2$ cardinality sets.

if $m = 1$ then $S_1$ will be one of all $1$ element sets, Then $S_1$ will be connected to all other $1$ cardinality sets and at least one $3$ cardinality set.

We can argue that, one $m$ (even) cardinality set is at least connected to one $(m-2)$ cardinality set. That particular $(m-2)$ cardinality set is at least connected to one $(m-4)$ cardinality set and so on till $\phi$ set vertex. There for all even cardinality sets are connected to $\phi$ directly or indirectly. 

A similar argument holds for odd cardinality set vertices till we reach some $1$ cardinality set. Moreover all 1 cardinality sets are connected

Therefore we have a situation now that all even cardinality sets form one connected component and all odd cardinality set form another component.

For example : $n = 4$ :

edited by
30 votes
30 votes
Best way to solve this for GATE is to take $n=2$ and $n=3$ and we get degree of each vertex = ${}^nC_2$ and no. of connected components = $2$.

Lets do it more formally.

It is clear {} should get connected to all $2$ element subsets (and not to any other) of $S$. So, degree of the corresponding vertex is ${}^nC_2$ as we have ${}^nC_2$ ways of choosing 2 elements from $n$. So, answer to first part must be this as it is given degree of all vertices are same.

Now, for the second part, from the definition of $G$ all the vertices of cardinality $k$ will be disconnected from all the vertices of cardinality $k-1$. This is because either all the $k-1$ elements must be same in both or $k-2$ elements must be same in both or else the symmetric difference will be more than $2$. Now if $k-1$ elements are same, symmetric difference will just be $1$. If $k-2$ elements are same, we have one element in one set not in other and $2$ elements in other set not in this, making symmetric difference $3$. Thus symmetric difference won't be $2$ for any vertices of adjacent cardinality  making them disconnected.

All the vertices of same cardinality will be connected - when just one element differs. Also, vertices with cardinality difference 2 will be connected- when 2 new elements are in one vertex. Thus we will be getting $2$ connected components in total.

.
28 votes
28 votes

set {1,2,3} 

power set { {}, 1 ,2,3, {1,2}, {2,3} ,{1,3}, {1,2,3,} }

according to property above diagram is gnerated .

Now You can ans both the questions.

6 votes
6 votes
This question can be approached in following way too.

We know that we can represent subset $S_i$ of $S$ where $|S|=n$ using $n-length$ binary string $B_i$.

Where $B_i[j] = 1$ iff $j^{th}$ element of set $S$ does belong to $S_i$.

Now, Degree of a given vertex is just number of different $n-length$ binary string we can make using just toggling exactly 2 element from binary string corresponding to given vertex.

There are $n\choose2$ ways of selecting 2 bits which needs to be toggled so subsequently there are $n\choose2$ neighbours of given vertex.

Now for number of connected component note that parity of bit-string remains same after toggling(here togling means $0$ to $1$ or $1$ to $0$ no other action.) exactly 2 bits.

So odd-parity bit string forms 1 connected component and even-parity bit string forms 1 connected component so total 2 CC.

Related questions

60 votes
60 votes
6 answers
1
Kathleen asked Sep 14, 2014
13,357 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,585 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,069 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...