A Hamiltonian Cycle is a simple path beginning and ending at the same vertex that visits every node exactly once. Remember that in a simple path repeated edges are not allowed. DHC = {(D) | D is a directed graph that contains a Hamiltonian Cycle} HC = {(G) | G is a undirected graph that contains a Hamiltonian Cycle } Prove that DHC HC Hint, for every node, v, in the directed graph D replace it with three nodes, in, mid, out, in the new undirected graph, G. Add edges (in,, midi) and (midi, out;) to G. Now for every edge, (u, v), in D add and edge from (outu, inv) to G.