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

How many connected components does $G$ have?

### 6 Comments

Every vertex in G has the same degree.

And that degree is $nC2$, which is more than $\frac{n-1}{2}$.

So how come the whole graph is not connected, given the theorem here?

https://gateoverflow.in/130614/discrete-math-2-5

Is that because n has to be strictly even?

Please have a look? @Bikram, @Arjun, @dd, @Lakshman Patrel RJIT

## 6 Answers

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

- Both green shaded area has one element each and in this case sizes of $S_1$ and $S_2$ are same.
- 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$.
- 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.

**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)$.**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.**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$ :

### 12 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)

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

Edited

Got it thanks

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.

.

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.

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.**