Consider a graph $G$ with vertex set $V$ and edge set $E$. Suppose that $V = \mathcal{P}(\{1, 2, 3\})$, and that $\{S, T\} ∈ E$ if and only if $|S − T| + |T − S| = 1$.

(a) List all the edges in the set $E$. (b) What are the neighbours of the vertex $\{3\}$? (c) What is the neighbourhood of $A = \{\{1\}, \{1, 2\}\}$? (d) What is the degree of the vertex $\{1, 2\}$? (e) Draw the graph $G$. (f) Find a path from $\{1, 2\}$ to $\{3\}$?

<aside> 💡 (a) To determine all the edges in the set $E$, we need to find all pairs of subsets $S, T$ of $\{1, 2, 3\}$ such that $|S − T| + |T − S| = 1$. We can do this by checking each possible pair $(S, T)$ and verifying the condition. Alternatively, we can note that there are only two possible values for $|S − T|$ and $|T − S|$, namely $0$ and 1, and that their sum is always odd. Therefore, $|S − T$| and $|T − S|$ cannot both be $0$, and exactly one of them must be $1$. This means that $S$ and $T$ differ by exactly one element, i.e., they are either disjoint or have exactly one element in common. Thus, the edges in $E$ are:

$$ \{ \{1\}, \{1, 2\} \}\\ \{ \{1, 2\}, \{2, 3\} \}\\ \{ \{2\}, \{1, 2\} \}\\ \{ \{2\}, \{2, 3\} \}\\ \{ \{3\}, \{2, 3\} \}\\ \{ \{1, 3\}, \{1, 2, 3\} \}\\ \{ \{2\}, \{1, 3\} \}\\ \{ \{1\}, \{1, 3\} \}\\ $$

(b) The neighbors of the vertex $\{3\}$ are the subsets that differ from $\{3\}$ by exactly one element. Thus, the neighbors of $\{3\}$ are $\{2, 3\}$ and $\{1, 3\}.$

(c) The neighborhood of $A = \{\{1\}, \{1, 2\}\}$ is the set of subsets that differ from either $\{1\}$ or $\{1, 2\}$ by exactly one element. Thus, the neighborhood of $A$ is $\{ \{1\}, \{1, 2\}, \{2\}, \{1, 3\}, \{2, 3\} \}.$

(d) The degree of a vertex is the number of edges incident to it. Therefore, the degree of the vertex $\{1, 2\}$ is the number of edges that contain either $\{1\}$ or $\{2\}$, since these are the only subsets that differ from $\{1, 2\}$ by one element. There are three such edges, namely $\{ \{1\}, \{1, 2\} \}, \{ \{1, 2\}, \{2, 3\} \},$ and $\{ \{1\}, \{1, 3\} \}.$ Therefore, the degree of $\{1, 2\}$ is $3.$

(e) Here is a drawing of the graph $G$:

     {1} ----- {1,2} ----- {2} ----- {2,3}
      |           |          |          |
      |           |          |          |
     {1,3} -----{1,2,3}---- {3} -------

(f) To find a path from $\{1, 2\}$ to $\{3\},$ we can use the following sequence of edges:

$\{ \{1, 2\}, \{2, 3\} \}, \{ \{2, 3\}, \{3\} \}$

This path starts at $\{1, 2\},$ which is connected to $\{2, 3\},$ which is connected to $\{3\}.$ Therefore, the path goes from $\{1, 2\}$ to $\{3\}.$

</aside>