I am looking at the following solved exercise:
A cycle $C$ in a graph is called simple, if no vertex in $C$ is appeared more than twice. For example a hamiltonian cycle is a simple cycle, that goes through every vertex of a graph. The HALF-SIMPLE-CYCLE (HSC) Problem asks if in a graph with $n$ vertices there is a simple cycle of length $\geq \frac{n}{2}$. Show that HSC is NP-complete.
The solution is the following:
Let $G=(V,E)$ a graph with $V=\{1, \dots, n\}$. We add to $G$ $n$ vertices, but no other edges. That means that we define $V'=\{1, \dots , 2n\}$ and $G'=(V',E)$. Then it holds that $G\in \text{ HAM } \Leftrightarrow G'\in \text{ HSC }$.
$$$$
First of all, to show that the problem is NP-complete, we have to show that it is NP and that it is NP-hard, right?
$$$$
To show that the problem is in NP, we do the following:
A non-deterministic Turing machine guesses a cycle of length $\geq \frac{n}{2}$ and checks if this cycle is simple. This takes linear time, which is equal to the size of the cycle. Is this correct?
$$$$
Then to show that the problem is NP-hard, we want to reduce the HAM Problem to the HSC Problem.
The HAM Problem is to determine if there is a simple path that crosses each vertex of the graph.
When we consider for the HSC Problem a graph $G'$ that is created by $G$ when we add $n$ more vertices, without edges, we have the following:
When $G$ is in HAM, we know that there is a simple path that crosses each vertex of the graph. That means that for $G'$ there is a simple path that crosses the half number of all vertices of the graph, so $G'$ is in HSC.
Is this correct?
Is this an iff statement, or do we have to prove also the other direction?
The parts you mentioned are correct.
If we find a simple cycle of length at least $\frac{n}{2}$ in $G'$, this immediately shows that $G$ contains a hamilton-cycle because $G$ must contain a simple cycle with length $n$.
So, yes , the last statement is an iff-statement.