# How to show a graph contains no Hamilton cycles?

#### Yuuki

##### Member
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

##### Well-known member
MHB Math Helper
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<<.

#### Yuuki

##### Member
Thank you for the reply for this thread and the other one.