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