(a) Prove that, for any integers m > 3 and n ≥ 2, the Cartesian product Cm Pn is Hamiltonian, where Cm is the cycle of length m and P is the path of length n1. Present your proof by explicitly giving a Hamilton cycle of Cm Pn. [4 marks] (b) Using the result in (a), prove that for any Hamiltonian graph G and any nontrivial graph H which contains a Hamilton path the Cartesian product G H is Hamiltonian. [4 marks]

Fig: 1