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

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.

• Say you have a vertex corresponding to the empty subset of S. What subsets are adjacent to it? Oct 24, 2018 at 12:00
• 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. Oct 24, 2018 at 12:04
• 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 {}? Oct 24, 2018 at 12:06
• Ivan Neretin I've updated my comment. Oct 24, 2018 at 12:32
• 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? Oct 24, 2018 at 12:34

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.

• So if two sets (vertices) $A$, $B$ are connected iff their $|A\Delta B|=k$ then degree if each vertex is ${n\choose k}$? Jul 16, 2020 at 13:22
• Yes, that's correct. Jul 16, 2020 at 14:28

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.