# Hamiltonian circuits / graphing

Can someone tell me if I'm correctly doing these graphs for Hamiltonian circuits?

I know that you start at the root node and show the path "back" in a tree. But what if it crosses and such. I'm just confused at how to actually know if it's right or wrong.

• What do you know, $v_4$ is of degree 1, so the whole graph has no Hamiltonian circuit! Feb 28 '18 at 15:16
• I apologize the graph is supposed to connect with v9, I'll correct it @ParclyTaxel Feb 28 '18 at 15:36

FindHamiltonianCycle[UndirectedGraph[{1->2,1->5,2->3,2->8,2->7,3->4,3->8,4->9,5->6,5->10,6->7,6->11,7->8,8->9,9->12,10->11,11->12}]]

A standard strategy when you're looking for a Hamiltonian cycle in a very sparse graph is to look at the vertices of degree $2$. If there is any Hamiltonian cycle, it is forced to use both edges out of such a vertex, which either limits the search space significantly or just forces a contradiction outright.
In your graph, we know that any Hamiltonian cycle would have to use the edges $v_1v_2$ and $v_1v_5$ (the only two edges incident to $v_1$), the edges $v_5 v_{10}$ and $v_{10} v_{11}$ (the only two edges incident to $v_{10}$), and the edges $v_{11}v_{12}$ and $v_9 v_{12}$ (the only two edges incident to $v_{12}$).
Including these edges saturates the vertices $v_5$ and $v_{11}$ in the process: there can be no other edges in the Hamiltonian cycle incident to these vertices. But now there is only one remaining edge it's possible to take out of vertex $v_6$: the edge $v_6v_7$. As a result, there does not exist a Hamiltonian cycle.