Number of cycles of length 4 in the n-cube? How would I do this problem? I know that I have to consider pair of strings that differ in exactly 2 positions, but I am stuck beyond this. 
 A: Let $G=(V,E)$, where $V=\{0,1\}^n$, and $E=\{(a,b)\in V\times V:a\text{ and }b \text{ differ in only one place}\}$. How to construct cycle of length $4$? Pick any vertex $v=v_1$, change any digit, let's say $i$-th, obtaining $v_2$. Then change any other digit ($j$-th) to get $v_3$, and return to $v_1$ using the only remaining path (changing $i$-th digit to get $v_4$, and then $j$-th). There are $2^n$ vertices and we have $n(n-1)$ ways to choose $i$ and $j$, so there are $$2^nn(n-1)$$ such cycles. If we identify cycles such as $(v_1,v_2,v_3,v_1)$ and $(v_2,v_3,v_1,v_2)$, then we are counting each $4$ times, and there are $$2^{n-2}n(n-1)$$ such cycles. Also if we identify cycles going in opposite directions, then we count each twice yielding $$2^{n-3}n(n-1)$$ unique cycles.
A: We use induction on $n$. For $n=1$ the claim is obviously true. Now suppose the claim holds for all hypercubes of dimension $k \leq n$ and consider the hypercube $Q_{n+1}.$ We can naturally split the cube into two smaller cubes $Q_n^0,Q_n^1.$ There are three types of $4$-cycles in $Q_{n+1}.$ Those in $Q_n^{0}$ and $Q_n^1$ and those having some edges in $Q_n^{0}$ and some edges in $Q_{n}^1.$ The later $4$-cycles are obtained by taking an edge in $Q_{n}^0$ the copy of this edge in $Q_{n}^1$ and the incident edges. Hence there is a unique such a cycle for any edge in $Q_{n}^0.$ Using the induction hypothesis we thus have a total of $$ 2\cdot (n-1)n2^{n-3} + 2^{n-1}n = (n-1)n2^{n-2}+2^{n-1}n = 2^{n-2}n(n+1) $$ as desired.
