Finding Hamiltonian cycles in polynomial space

Question: If $H = \{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\}$ ($m$ is in binary), prove that $H \in$ polynomial space.

My thoughts: I thought that I could show that $H \in NP$, by which it would automatically follow that $H \in$ polynomial space. By the witness theorem, the $m$ distinct Hamiltonian cycles (call them the set $C$) would serve as a witness. However, what is not apparent is if $|C| \leq |G|^k$. In fact, that is the entire problem, isn't it? What am I thinking about wrong over here?

Observe that a naive witness for $m$ cycles is a list of the cycles, which may be exponential (in case the value of $m$ is exponential in the size of $G$).

So perhaps you should work directly with PSPACE.

A possible approach is to order the vertices of $G$, and then try all sequences of $n$ (the number of vertices) vertices, in lexicographical order (one at a time, erasing the last one every time you proceed to the next, so as not to waste space), and for each sequence check whether it is a Hamiltonian cycle, and increment a counter if it is. If the counter passes $m$ then you have $m$ distinct cycles.

If by "distinct cycles" you mean that you do not count cyclic permutations, then after you complete the entire count, simply divide the number of cycles you found by $n$, giving you the number of cycles without cyclic permutations, and compare this number to $m$.

StackExchange Computer Science Q#11698, answer score: 3