I'm taking my first Graph Theory course now as a undergrad. I may not be the best person to answer this question. However, it's been sitting in the Urgent Homework Help forum for over 24 hours. Even if I can't give a complete solution, maybe I can put you on the right path.

Consider the process of constructing a (k+1)-cube from a k-cube. Suppose the vertices of a k-cube G are labeled . Let G' be a duplicate of G with the vertices labeled . Add edges between and , and , and and so on. The resulting graph is a (k+1)-cube.

The vertices have doubled in going from k to k+1, so the 2^k should be provable with induction.

Since I didn't know how many edges the k-cube had, it took a little while for me to tease out that "k2^k-1" meant . Try using the MATH tags next time or putting the exponent in parentheses. Anyway...

Again, I think induction is the way to go. Edgewise, when you go from the k-cube to the (k+1)-cube, you double the number of edges in the k-cube, then add a number of edges equal to the number of vertices in the k-cube. The first few terms of this sequence (starting with the 2-cube aka square):

4

Starting with , the first few terms of the sequence are:

Yikes. My sketchy explanation turned out sketchier than I'd thought, but I hope it helps get you started towards a proof.

Wil