I've been learning about proving NP-completeness via reduction, and came across the following problem:
Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using $\ge \frac{1}{2}$ of the vertices is a NP-Complete problem.
The first part is to show that the above problem is in NP. That's simple enough, since a solution is verifiable in linear time by just traversing through the vertices to ensure they form a cycle, and that the no. of vertices in the solution set are $\ge \frac{1}{2}$ of the total no. of vertices.
As far as polynomial-time reduction...my thoughts so far are that you can probably reduce Hamiltonian circuit problem to it, but I'm unsure how to proceed. I suppose that, given the original graph $G$, you could first check whether the entire graph is a Hamiltonian circuit. Then if not, you could delete a random vertex from $G$ (there are a total of $|V|$ ways of doing this), and check for Hamiltonian circuit again...then if not, delete two vertices from G (there are $\binom{|V|}{ 2}$ ways of doing this), and check again for Hamiltonian circuit...and so on, all the way down to deleting $\frac{|V|}{2}$ vertices from $G$. But reducing it this way sounds cumbersome, and may even be an exponential-time reduction.
Any help would be appreciated.