# Graph theory

• Feb 4th 2009, 08:04 PM
jzellt
Graph theory
How do I show that the k-cube has 2^k vertices and k2^k-1 edges?

• Feb 5th 2009, 06:59 PM
wil
k-cube vertices and edges (rough explanation)
Quote:

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 $\displaystyle v_1,v_2,\ldots,v_{2^k}$. Let G' be a duplicate of G with the vertices labeled $\displaystyle v'_1,v'_2,\ldots,v'_{2^k}$. Add edges between $\displaystyle v_1$ and $\displaystyle v'_1$, $\displaystyle v_2$ and $\displaystyle v'_2$, $\displaystyle v_3$ and $\displaystyle 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 $\displaystyle 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
$\displaystyle 2\cdot4+4=12$
$\displaystyle 2\cdot12+8=32$
$\displaystyle 2\cdot32+16=80$

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

$\displaystyle 2 \cdot 2^{2-1}=4$
$\displaystyle 3 \cdot 2^{3-1}=12$
$\displaystyle 4 \cdot 2^{4-1}=32$
$\displaystyle 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