# Math Help - Graph theory

1. ## Graph theory

How do I show that the k-cube has 2^k vertices and k2^k-1 edges?

2. ## k-cube vertices and edges (rough explanation)

Originally Posted by jzellt
How do I show that the k-cube has 2^k vertices and k2^k-1 edges?
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 $v_1,v_2,\ldots,v_{2^k}$. Let G' be a duplicate of G with the vertices labeled $v'_1,v'_2,\ldots,v'_{2^k}$. Add edges between $v_1$ and $v'_1$, $v_2$ and $v'_2$, $v_3$ and $v'_3$ 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 $k \cdot 2^{k-1}$. 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
$2\cdot4+4=12$
$2\cdot12+8=32$
$2\cdot32+16=80$

Starting with $k=2$, the first few terms of the $k \cdot 2^{k-1}$ sequence are:

$2 \cdot 2^{2-1}=4$
$3 \cdot 2^{3-1}=12$
$4 \cdot 2^{4-1}=32$
$5 \cdot 2^{5-1}=80$

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

Wil