Non-deterministic algorithm for solving figure of 8 I am struggling in trying to figure out a non-deterministic algorithm for the following problem.

Consider the following problem, called the ﬁgure-of-eight problem (FOE). An instance is an undirected graph $G = (V,E)$ with vertices $V$ and edges $E$. $G$ is a yes-instance if there is a sequence of vertices $(v_{0},v_{1},...,v_{k+1})\ (some\ k \geq 6)$ such that

• Each pair $(v_{i},v_{i+1})$ is an edge $(each\ i &lt; k − 1)$ and $(v_{k−1},v_{0})$ is an edge. 

• Every vertex in $V$ occurs at least once in the sequence. 

• There is $j$ with $2 &lt; j &lt; k − 2$ such that $v_{0} = v_{j}$. 

• No other vertex in the sequence is counted twice, i.e. if $v_{s} = v_{t} (any\ s,t &lt; k)$ then either $s = t$ or ${s,t} = {0,j}$.

If there is no such sequence of vertices then $G$ is a no-instance of FOE.

Thanks
If you want to prove that this problem is in NP, then all you have to do is to come up with a polytime algorithm that verifies the correctness of a solution.  I.e., in polynomial time, verify that a given sequence satisfies the conditions you wrote.

This should also help you in actually construct the non-deterministic algorithm.