Let $Q_k$ be the graph whose vertex set corresponds to the set of all $01$-sequences of length $k$ with an edge between two vertices if the sequences differ in exactly one place.
Draw $Q_3$.(DONE)
Determine (with reasons) $e(Q_k)$ and show that $Q_k$ is bipartite.
My solution so far:
$d(G) = 2\cdot \frac{e(G)}{|G|}$ for a graph $G$.
So $e(Q_k)= \frac{1}{2} \cdot d(Q_k) \cdot |Q_k| $
Now $|Q_k| = 2^k$ since for a $01$ sequence of length $k$ we have two choices (0 or 1) for each position in the sequence, giving us
$|Q_k| = 2 \cdot 2 \cdot ... \cdot2$ (k times) $=2^k$.
Now, I am not sure how to work out $d(Q_k)$, the average degree of $Q_k$. From drawing $Q_3$ which has $d(Q_3)=3$, I can guess $d(Q_k)=k$. But how would I go about proving this?
Also any hints on how to show $Q_k$ is bipartite?
Note: If anything is unclear in the question or solution, please let me know and I will clarify it.