If the number of edges in an $n$-cube (also denoted as $Q_n$) is $k$, what is the number of edges in an $(n+1)$-cube (denoted as $Q_{n+1}$)? Express your answer in terms of $k$ and $n$.
How can I solve this problem? I am thinking about use handshaking theorem to solve this one but still do not know how.
We can take that the vertices of a $n$-cube can be labeled by bit strings of length $n$, from $00...0$ to $11...1$, so that two vertices are connected if and only if their corresponding strings differ exactly in one bit. This will simplify the answer significantly. (These numbers are actually coordinates in a system with its origin at one chosen vertex and the coordinate axes going along the edges from this vertex. Example: a $2$-cube = square: $\begin{matrix}00 & 01\\ 10 & 11 \end{matrix}$.
Note that the edges follow the above mentioned rule.)
We can see easily that the number of vertices are $\Rightarrow$ vertices$_n =2^n$. It follows from the above that we can consider it as a n-regular graph of order $2^n$. However, if we just multiplied the number of vertices by the degree, we would count every edge twice. Hence, taking one half of this, we have edges$_n$ =vertices$_n\times$ n $\times \frac{1}{2}$. Here $n$ is the degree. So we have edges$_{n} = n\times 2^{n-1}$.
Thus, we have edges$_{n+1} = (n+1)\times 2^n =\frac{2(n+1)}{n}$edges$_{n}$. Hope it helps as in the last answer I multiplied by one degree less, but the idea was the same as intended.