MHB How to show a graph contains no Hamilton cycles?

[annie122]

Here is the graph in question:

The edges in red are the paths that must be included in the cycle, since vertices
a, k, e, and o have only degree 2.
I listed all possible routes starting from vertex b, and showed that they all routes closes a cycle while leaving some vertex disconnected.

Is there a more efficient way?
In general, when asked to show that a graph doesn't contain something, what is the usual procedure for proving it?

 

[Sudharaka]

Here is the graph in question:

The edges in red are the paths that must be included in the cycle, since vertices
a, k, e, and o have only degree 2.
I listed all possible routes starting from vertex b, and showed that they all routes closes a cycle while leaving some vertex disconnected.

Is there a more efficient way?
In general, when asked to show that a graph doesn't contain something, what is the usual procedure for proving it?

Hi Yuuki, :)

Several algorithms to solve this kind of a problem is discussed >>here<<. Specially you might like to read >>this<<.

 

[annie122]

Thank you for the reply for this thread and the other one.
I'll definitely read the PDF.

 

[Sudharaka]

Thank you for the reply for this thread and the other one.
I'll definitely read the PDF.

You are welcome. (Handshake)