in Set Theory & Algebra edited by
6,313 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?
in Set Theory & Algebra edited by
6.3k views

4 Comments

@JashanArora here graph has $2^{n}$ vertices not $n$..

0
0
Can someone provide easy solution to this question?
1
1
Consider this, two vertices are adjacent iff the symmetric difference is 2 that is the number of elements not common=2, also the degree of all vertices are same which means the degree of phi is equal to degree of all the vertices and the degree of phi is equal to number of subsets with 2 elements hence nC2.
3
3

6 Answers

52 votes
52 votes
Best answer

$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
by

4 Comments

@ajaysoni1924 in case 1) as we can see (m-1) elements will be common in both sets between S1 and S2 and size of both sets will also be same. .
Now we have to find number of such S2's , for that we will select (m-1) out of m elements (as any of (m-1) can be common) $\left(\begin{array}{c}m\\ m-1\end{array}\right)= m$ and now for the m th element we have (n-m) choices ..So its m(n-m) 

4
4
edited by

@Punit Sharma brother can you explain little bit more by an example, I am not getting this.

Edited

Got it thanks

0
0
thanku @dd for such a beautiful answer of this question
1
1
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.

.
by

2 Comments

@arjun sir.. i am not being able to understand this. what is the better way to understand this? or which resourse i should refer to learn this question topic?
0
0
@sheshang you can read the answer given by Debashish . it is very clearly described.
0
0
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.

1 comment

Hi,

Here using the diagram its easy to calculate for the 2 or 3 element set, but for higher order set how can we derive the degree of the vertices and number of connected components?
0
0
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.

2 Comments

Amazing way to look at the question!!
0
0
The way you interpreted this question is very amazing. Thanks for explanation in simple and logical way. I just bypass this question by seeing the line "All vertices have same degree"  and just calculated number of neighbours of phi which is nc2 or two elements subsets. Thanks again for explaining.
0
0

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true