Combinatoric Graph

Question

Draw a graph whose nodes are the subsets of {a,b,c} and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element? I'm having a really hard time understanding this problem, let alone executing it correctly. Anyone have any thoughts?

Answer 1

Let $v_1=\{\}$, $v_2=\{a\}$, $v_3=\{b\}$, $v_4=\{c\}$, $v_5=\{a,b\}$, $v_6=\{a,c\}$, $v_7=\{b,c\}$ and $v_8=\{a,b,c\}$. We see that two vertices are adjacent if and only if their subsets differ by exactly one element. That is, if the symmetric difference of any two sets contains only one element, then they are adjacent. Thus $v_1$ is adjacent to $(v_2,v_3,v_4)$, $v_2$ is adjacent to $(v_1,v_5,v_6)$, $v_3$ is adjacent to $(v_1,v_5,v_7)$, $v_4$ is adjacent to $(v_1,v_6,v_7)$, $v_5$ is adjacent to $(v_2,v_3,v_8)$, $v_6$ is adjacent to $(v_2,v_4,v_8)$, $v_7$ is adjacent to $(v_3,v_4,v_8)$ and $v_8$ is adjacent to $(v_5,v_6,v_7)$. The following graph is a $3$-regular graph of order $8$.

Answer 2

Start by listing out the possible subsets of $\{a, b, c\}$. So an example of three vertices are $v_{1} = \{a\}$, $v_{2} = \{a, c\}$, $v_{3} = \{c\}$. The vertices $v_{1}, v_{2}$ are adjacent, because they differ by one element. The same stands for vertices $v_{2}$ and $v_{3}$. However, $v_{1}$ and $v_{3}$ are not adjacent, as $v_{1}$ does not have a $c$ and $v_{3}$ has neither $a$ nor $b$.