2
$\begingroup$

What would be the most reliable (and preferably simplest) way to determine and prove if this graph is Hamiltonian or not?

My first thought was to try and draw out the circuit but I feel that can be easily done wrong? I was also thinking of seeing if the graph includes all Hamiltonian properties?

Is this graph Hamiltonian and what was your approach?

Thanks

enter image description here

*Removed 3 middle vertices, resulting 4 components:

enter image description here

$\endgroup$
4
$\begingroup$

If you delete the three middle vertices in the central row, the graph splits into four connected components. Therefore the graph does not have a Hamiltonian cycle.

$\endgroup$
10
  • $\begingroup$ Oh, is your approach to dispute the proposition that "If G is a Hamiltonian graph, then deleting any K vertices from G results in a graph with a most K connected components?What would the resulting components look like? $\endgroup$ – bec7 May 17 at 11:45
  • 1
    $\begingroup$ Also if you delete the middle five vertices, the remaining graph has eight components, so it doesn't have a Hamiltonian path either. $\endgroup$ – Joffan May 17 at 11:48
  • $\begingroup$ @A825 I don't think that proposition is in dispute; it's just being applied to the graph you presented. $\endgroup$ – Joffan May 17 at 11:52
  • $\begingroup$ Ah I see, so if I remove the middle 3 vertices, what do the 4 components look like? I'm having a hard time visualising it $\endgroup$ – bec7 May 17 at 11:53
  • 1
    $\begingroup$ @A825 Yes, that looks correct now. $\endgroup$ – Jaap Scherphuis May 17 at 13:00
3
$\begingroup$

The easiest way to prove that a Graph is Hamiltonian, by just finding any Hamiltonian path.

Proving the inverse is not that easy. The only way I know is to somehow argue logically that if you first choose one edge then you can't choose a specific other edge which will somehow give a contradiction. You can try argue using degrees of nodes as well.

However, there is no general approach, as finding a Hamiltonian path is a NP-complete problem - meaning it's probably not solvable in polynomial time.

$\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.