Recall that the k-cube is the simple graph whose vertices are all sequences (a1,...,ak) with each ai either 0 or 1, and where two vertices are adjacent precisely if their sequences dier at exactly one place.

(a) Let k 2. Show that Qk has two subgraphs G0 and G1, each isomorphic to Qk1, having no vertices or edges in common, and that each vertex of G0 is adjacent to one vertex of G1. Hint: Consider the vertices with last coordinate ak = 0 resp. ak = 1, and the edges between them.

(b) Use induction to prove that Qk is Hamiltonian for each k 2. Hint: In the induction step, use the subgraphs G0 and G1 from part (a).

Advice: it may be helpful to do this for k = 3 using a drawing of the graph, in order to get an intuition for the general case. For part (b), you are allowed to use the result in (a) even if you havent managed to prove it.