We reduce from Hamiltonian cycle. Given a graph $G$, we construct new labelled graph as follows:
- Label each vertex of $G$ by $\mathrm{A}$
- To each vertex of $G$ connect it with a hanging vertex "above" it and label this vertex by $\mathrm{F}$
- For each edge $e$ of $G$, add a "middle" vertex labelled by $\mathrm{K}$, and connect each "middle" vertex to the two $\mathrm{F}$ vertices above the two $\mathrm{A}$ end points of its corresponding edge.
The sequence will be $\mathrm{AFKAFK}\dots\mathrm{AFK}$$KKK..\dots KKK$ where we repeat the pattern $\mathrm{AFK}$ the number of times equal to the number of vertices of $G$, i.e. $|V(G)|$. And the number of trailing $\mathrm{K}$ (written in italic for clarity) equals $|E(G)|-|V(G)|$, i.e. after finishing the Hamiltonian cycle, the traversal needs to come back and collect the remaining "middle" vertices.
If $G$ is Hamiltonian, clearly we can order the neighborhood of each vertex so that the edge that will be taken at each vertex is in accordance with the Hamiltonian cycle.
Conversely, if we can order the neighborhood of each vertex and choosing a string vertex so that the preorder traversal prints out the required sequence then we can follow the path delineated by the traversal to figure out the Hamiltonian cycle. Indeed, if at some point you get stuck, then there would be the very FIRST time you get stuck somewhere. But clearly, if so, you need to produce a $\mathrm{KK}$ before the trailing "garbage" sequence begins. In short, you cannot get way back and branch (at least for the FIRST time) without printing out a $\mathrm{KK}$.
