Consider the following decision problem: . Alternating-Hamiltonian-Cycle: Given a graph G-(V,E), and a subset A ? V of its vertices, does there exist a Hamiltonian Cycle of G, such that the cycle alternates between vertices in A and vertices in V\A? For example, if V-{ai, a2, ??, b?, b2, b3} and A-al, a2, ??}, and there were edges between every vertex, then the answer would be YES, because ai, bi, a2,12, ??, b3, ai is both a Hamiltonian cycle and alternates between vertices in A and vertices not in A (i) Prove that Alternating-Hamiltonian-Cycle NP (ii) Prove that Alternating-Hamiltonian-Cycle E NP Hard (iii) Thereby prove that Alternating-Hamiltonian-Cycle& NP Complete Consider the following decision problem: . Alternating-Hamiltonian-Cycle: Given a graph G-(V,E), and a subset A ? V of its vertices, does there exist a Hamiltonian Cycle of G, such that the cycle alternates between vertices in A and vertices in V\A? For example, if V-{ai, a2, ??, b?, b2, b3} and A-al, a2, ??}, and there were edges between every vertex, then the answer would be YES, because ai, bi, a2,12, ??, b3, ai is both a Hamiltonian cycle and alternates between vertices in A and vertices not in A (i) Prove that Alternating-Hamiltonian-Cycle NP (ii) Prove that Alternating-Hamiltonian-Cycle E NP Hard (iii) Thereby prove that Alternating-Hamiltonian-Cycle& NP Complete