## calliendra 2 years ago For a theoretical graph, the n-th cube Q_n is a simple graph whose verices are the 2^n points (x_1...x_n) in R^n. So that for each x_i=0 or 1, and whose two vertices adjacent if thet agree in exactly n-1 coordinates. show that if n>=2 the Q_n has a hamiltonian cycle.

1. calliendra

• ok. so i am going to use induction and i hasve my base step be N=2 so i have a 2 dimensional cube with 2^2=4 vertives in R^2. with coordinates (00) (01) (10)(11)... which is really a two dimensional square with those coordinates as vertices. i can easily see it is a hamiltonian cycle.true.

2. calliendra

i can even visualize a 3d cube whose eight vertices in R3whose edges are named: (000)(001)(010)(100)(011)(101)(110)(111) create a cube. which creates a hamiltonian cycyle. |dw:1383750838900:dw|

3. calliendra

however when i get to the n and n+1 i can't think of it... i don't know how to PROVE there is a hamiltonian cycle ... unless there is some formula that i can find to guarantee the edge numbers i need....