Welcome to our community

Be a part of something great, join today!

How to show a graph contains no Hamilton cycles?

Yuuki

Member
Jun 7, 2013
43
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
Feb 5, 2012
1,621
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
Jun 7, 2013
43
Thank you for the reply for this thread and the other one.
I'll definitely read the PDF.
 

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621