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?
-
$\begingroup$ First step: What are the subsets of $\{a,b,c\}$? $\endgroup$– Daniel MontealegreApr 15, 2014 at 22:08
-
$\begingroup$ {a}{b}{c}{a,b}{a,c}{b,c} and {} $\endgroup$– jerry2144Apr 15, 2014 at 22:09
-
$\begingroup$ Yes, although you are missing $\{a,b,c\}$. Then for each one draw a point and which do you connect to which? $\endgroup$– Daniel MontealegreApr 15, 2014 at 22:13
-
$\begingroup$ Your graph will look like a cube. Think of the vertices as ordered triples of zeros and ones, e.g., identify $\{a\}$ with $(1,0,0)$, $(a,c)$ with $(1,0,1)$, etc. Now think of each triple as the $(x,y,z)$-coordinates of a point in space. $\endgroup$– bofApr 15, 2014 at 22:37
2 Answers
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$.
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$.
-
$\begingroup$ would i include {} as a vertice and it would be adjacent to only the single element subsets? $\endgroup$ Apr 15, 2014 at 22:11
-
-
$\begingroup$ Yes, include $\{\}$ as a vertex (plural vertices), and join it to the one-element subsets. $\endgroup$– bofApr 15, 2014 at 22:15
-
$\begingroup$ What kind of shape am I going to get? I totally understand the question, but am now having troubles actually getting a graph created. Any help? $\endgroup$ Apr 15, 2014 at 22:23
-
$\begingroup$ I'm pretty sure this is a Hasse Diagram: en.wikipedia.org/wiki/Hasse_diagram $\endgroup$– ml0105Apr 15, 2014 at 22:24