1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ First step: What are the subsets of $\{a,b,c\}$? $\endgroup$ Apr 15, 2014 at 22:08
  • $\begingroup$ {a}{b}{c}{a,b}{a,c}{b,c} and {} $\endgroup$
    – jerry2144
    Apr 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$ Apr 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$
    – bof
    Apr 15, 2014 at 22:37

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ would i include {} as a vertice and it would be adjacent to only the single element subsets? $\endgroup$
    – jerry2144
    Apr 15, 2014 at 22:11
  • $\begingroup$ Yes. That is correct. $\endgroup$
    – ml0105
    Apr 15, 2014 at 22:13
  • $\begingroup$ Yes, include $\{\}$ as a vertex (plural vertices), and join it to the one-element subsets. $\endgroup$
    – bof
    Apr 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$
    – jerry2144
    Apr 15, 2014 at 22:23
  • $\begingroup$ I'm pretty sure this is a Hasse Diagram: en.wikipedia.org/wiki/Hasse_diagram $\endgroup$
    – ml0105
    Apr 15, 2014 at 22:24

Not the answer you're looking for? Browse other questions tagged .