Let's define two languages as follows: EULER-CYCLE = {G: G has an Eulerian cycle} HAM-CYCLE = {G: G has an Hamiltonian cycle} where G is a graph....

Let's define two languages as follows:

EULER-CYCLE = {<G>: G has an Eulerian cycle}

HAM-CYCLE = {<G>: G has an Hamiltonian cycle}

where G is a graph. An Eulerian cycle traverses each edge exactly once. A Hamiltonian cycle visits each vertex exactly once. In both cases, the cycle must start and end on the same vertex. Show that EULER-CYCLE is polynomial time reducible to HAM-CYCLE.