# How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:

1. Write a list of $x$ numbers $p_1, p_2, p_3 ... p_x$, where $x$ is the number of nodes in $G$. Each number in this list is non-deterministically selected to be from 1 to $x$.

2. Check for repetitions in this list. If a repetition exists, reject.

3. Check whether both $s = p_1$ and $n = p_x$. If either do not hold, reject.

4. For each $i \in [1, x - 1]$, check whether $(p_i, p_{i + 1})$ is an edge of $G$. If any are not, reject.

5. Accept.

I do not understand how this algorithm works. Specifically, in step 1, why am I making a list of random (potentially repeating) numbers from 1 to $x$ (What does this list have to do with the nodes of $G$?)?

Likewise, in step 4, why does $(p_i, p_{i + 1})$ represent a potential edge in $G$?

1. Each $p_{i}$ should be a label for a vertex in $G$. Typically $p_{i} \in [1,x]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p_{i},p_{i+1})$ could be an edge).
So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.