4. (3 points) Recall that Hamiltonian Cycle problem is defined as follows: - Input: An undirected graph G. - Question: Is G Hamiltonian (meaning that it contains a simple cycle that visits all the vertices)? 1 Let X be the following problem: - Input: An undirected graph G, and an integer k0. - Question: Can G be made Hamiltonian by adding at most k edges to it? First prove that XNP. Then prove that Hamiltonian Cycle pX