Complexity of "half cycle" I'm working on the following problem:
HALFCYCLE (HALFC):
Input:
A directed graph $G = (V,E)$.
Output:
Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.

Prove that if $\mathsf{PH} \ne \mathsf{coNP}$ then HALFCYCLE is not NP-complete.

I have no idea how to solve this implication.
Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.

How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$?
There are two options:


Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying NP=coNP.
Show that HALFCYCLE is in coNP. Since HALFCYCLE is NP-hard, in particular SAT reduces to HALFCYCLE, and so SAT is in coNP, implying NP=coNP.


(You can replace SAT with any NP-hard problem, and coSAT with any coNP-hard problem.)

Good luck!