1
$\begingroup$

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

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

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}]]
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.