Properties of a Powerset Graph

Let $n > 1$ be an integer and $A = \{1, \ldots,n\}$ and consider the graph with vertices

$V = \mathcal{P}(A)$

and edges

$E = \{\{S,T\}:|(S \setminus T) \cup (T \setminus S)| = 1\} $

a) What are the degrees of the vertices in $G$ ?

b) For what values of $n$ is $G$ bipartite?

c) For what values of $n$ does $G$ have an Euler circuit

d) For what values of $n$ is $G$ connected?

Mainly I have been stuck on understanding what the powerset of a graph means. An edge as multiple subsets of a powerset hasn't clicked in my head.

Solution 1:

We have a graph, where the labels of the vertices are subsets of $A$, and we connect two vertices if they have the same label, but one of them contains precisely one more element. Here is an example where $A=\{x,y,z\}$ (in our problem, it would be $\{1,2,3\}$; also, ignore the arrows):

Now, it is clear that degrees of the vertices here are all $3$. If we constructed the power set graph of $\{1,2\}$, we would find that all of their degrees are $2$. This should lead us to believe that the degrees of all of the vertices on the power set of $A=\{1,2,\dots,n\}$ is $n$.

Let $S\in \mathcal P(A)$ be some vertex of our graph, with $|S|=k$. This means that there are $n-k$ elements in $A$ but not in $S$. Adjoining any single of these elements to $S$ would give us an edge of $S$. Moreover, removing any single one of the $k$ elements of $S$ would also mean we have an edge of $S$. Therefore, there $S$ must have degree $n-k+k=n$. Since $S$ was arbitrary, all vertices have degree $n$.