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

Question

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.

Answer 1

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.

Answer 2

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.