Then G has two M-alternating Hamiltonian paths each starting at [w.sub.1] and ending at diametrically opposite vertices of the last canonical 4-cycle.

Proposition 2 (a) If d [greater than or equal to] 3 is odd, and v, v' are diametrically opposite vertices of [Q.sub.d], then [Q.sub.d] - v - v' has a Hamiltonian cycle.

(b) If d [greater than or equal to] 4 is even, and v, u are neighbors, and v, v' are diametrically opposite vertices of [Q.sub.d], and u, u' are diametrically opposite vertices of [Q.sub.d], then [Q.sub.d] - v - v' - u - u' has a Hamiltonian cycle.

An s-domino contains two pairs of opposite vertices.

Lemma 8 Every 4-total-coloring [C.sup.T] of an s-domino is such that, for one pair of opposite vertices x and y, the following holds: [C.sup.T] (x) = [C.sup.T] (y) and [C.sup.T] (x*) = [C.sup.T] (y*).