Question

Prove that the cartesian product of any two cycles is a Hamiltonian graph.

Answer 1

1

Explanation:

We show that the cartesian product C, x C„2 of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n, and n2 is at least two and there exist positive integers d,, d2 so that d, + d2 = d and g.c.d. (n,, d,) = g.c.d. (n2, d2) = 1