1
$\begingroup$

Let $S$ be a set of $n$ elements $\{1,2,\dots,n\}$ 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 $(R_1\setminus R_2) ∪ (R_2\setminus R_1)$

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

How many connected components does $G$ have?

================================================================

My take-I am able to solve it only by taking small example like take $n=2$ and $n=3$ and not able to understand the solution in formal way.

Please, explain how do I solve such question(s) formally.

Any help is highly appreciated in advance.

$\endgroup$
  • $\begingroup$ Say you have a vertex corresponding to the empty subset of S. What subsets are adjacent to it? $\endgroup$ – Ivan Neretin Oct 24 '18 at 12:00
  • $\begingroup$ say we have set {1,2,3} then power set { {}, 1 ,2,3, {1,2}, {2,3} ,{1,3}, {1,2,3,} }, vertices adjacent to {} are {1,2}, {2,3}, {1,3} iff the symmetric difference of the corresponding sets has exactly 2 elements. $\endgroup$ – Geeklovenerds Oct 24 '18 at 12:04
  • $\begingroup$ Yes, the power set looks like that (except that you should have said {1},{2},{3} instead of 1,2,3), but which of these subsets are adjacent to {}? $\endgroup$ – Ivan Neretin Oct 24 '18 at 12:06
  • $\begingroup$ Ivan Neretin I've updated my comment. $\endgroup$ – Geeklovenerds Oct 24 '18 at 12:32
  • $\begingroup$ Assume $n=2018$. Is there any path from the empty set to the total space? Is there any path from the empty set to $\{1\}$ and/or from $\{1\}$ to the total space? $\endgroup$ – dan_fulea Oct 24 '18 at 12:34
1
$\begingroup$

To find the degree of each vertex, you can compute the degree of {}, as Ivan Neretin proposed. So you have to ask yourself: which nodes are adjacent to {}? The answer is: all nodes with exactly two elements. So the node {} has degree $n*(n-1)/2$. Using the information given, we now know that all nodes must have this degree.

For the connectivity:

1): You can prove that for all $0 < i \leq n$ each node with exactly i elements is adjacent to any other node with exactly i elements. In other words: The induced subgraph containing all the nodes with exactly i elements is a complete graph.

2): You can also prove that there is no edge between two sets $A$ and $B$ if $|A| \not\equiv_2 |B|$.

3): If you have a set $A$ with $i < n - 1$ elements, then you can add two elements to that set such that you get a set $B$ with two more elements than $A$. Now it is clear that there is an edge between $A$ and $B$.

If you combine these facts, you will find that there are exactly 2 connected components in G.

$\endgroup$
1
$\begingroup$

Any subset $V$ of $S$ (so in a sense the vertices of $G$) can be described by a binary vector $v=(a_1,a_2,\ldots,a_n)$ with $a_i \in \{0,1\}, i=1,2,\ldots n$, where $a_i=1$ iff $i \in V$. This is a well known $1$-to-$1$ correspondence.

The symmetrical difference $\Delta$between 2 subsets $R_1$ and $R_2$ can be calculated by using the xor function on the vector entries: If $R = R_1 \Delta R_2$, then for the corresponding vectors we get $r_i= {r_1}_i {}$ xor ${r_2}_i$ for each component.

In order for the symmtrical difference of 2 subsets to have cardinality 2, the xor-function must have the value $1$ exactly 2 times. That means the vectors $r_1$ and $r_2$ must differ in exactly 2 positions.

For a given vector $r_1$, there are $n \choose 2$ possible choices for those 2 positions (let's say indices $p,q$). Since the vectors are binary, the positions alone determine the other vector $r_2$ completely: ${r_2}_i = 1 - {r_1}_i$ for $i \in \{p,q\}$ and ${r_2}_i = {r_1}_i$ otherwise.

So the answer to the first question is: Each vertex of $G$ has exactly $n \choose 2$ neighbours.

From this it is also clear that traversing from one vertex to one connected to it by an edge will not change if the number of $1$'s in the vector is odd or even. You change exactly 2 entries in the vector, either you change 2 $0$'s into 2 $1$'s or vice versa (increasing or decreasing the number of $1$'s by 2, resp.) or you change a $0$ into a $1$ and another $1$ into a $0$, for a net change of 0.

This means that there are at least 2 connected components, as $v_0=(0,0,\ldots,0)$ and $v_1=(1,0,0,\ldots,0)$ are not connected. But those 2 vertices are (together) connected to all other vertices: Given any $r=(r_1,\ldots,r_n)$, start with $v_0$ or $v_1$ according to parity, then, for $i=2,\ldots,n$, successively 'flip' the vector values at positions $1$ and $i$ if $r_i=1$. This means at the end all the vector values at positions $2$ to $n$ are the same, and because of parity the values at position 1 are also the same.

So this means the Graph has 2 connected components.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.