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.
(a) What is the number of edges and nodes in this graph? Can you name this graph? (b Is this graph connected? Does it have a perfect matching? Does it have a Hamilton cycle?
The answer's in the back on the textbook but I don't really understand it.
The graph should look like a cube: $8$ nodes, connected with $12$ edges.
It has a perfect matching. For each node in the set $\{\emptyset, \{a\}, \{b\}, \{a,b\}\}$, we can obtain its corresponding pair by appending $c$ to that node's set.
It has a Hamilton cycle. For example: $$ \emptyset \to \{a\} \to \{a,b\} \to \{b\} \to \{b,c\} \to \{a,b,c\} \to \{a,c\} \to \{c\} \to \emptyset $$