Hamiltonian circuits / graphing

54 Views Asked by At

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.

a simple planar graph on 12 vertices a tree of the paths from v_1

2

There are 2 best solutions below

0
On

Even with the correction, it appears there is no Hamiltonian cycle. I wouldn't expect it, with the low edge count you have there. Here's a Wolfram Language command that returns no cycle:

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}]]
0
On

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.