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.

Question

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.

anonymous · Answer

•  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.

anonymous · Answer

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|