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)

 

[blue_raver22]

To show that a graph does not contain a Hamilton cycle, there are a few different approaches that can be taken. One possible method is to use the definition of a Hamilton cycle, which states that it is a cycle that visits every vertex exactly once. Therefore, to prove that a graph does not contain a Hamilton cycle, we can show that there is at least one vertex that is not visited in any of the cycles in the graph.

In the given graph, we can observe that the vertices a, k, e, and o have a degree of 2, meaning that they are connected to exactly two other vertices. This means that any Hamilton cycle in this graph must include these four vertices, as they are the only ones that can be visited twice in a cycle. Therefore, one approach to proving that this graph does not contain a Hamilton cycle is to systematically go through all possible cycles starting from vertex b and show that they all leave at least one vertex disconnected.

Another approach that can be used is to use the concept of Hamiltonian paths. A Hamiltonian path is a path that visits every vertex exactly once, but does not necessarily form a cycle. In this case, we can try to find a Hamiltonian path in the graph that does not form a cycle. If such a path exists, then we can conclude that the graph does not contain a Hamilton cycle.

In general, to prove that a graph does not contain a certain property, it is important to understand the definition of that property and use it to systematically analyze the graph. This may involve finding counterexamples or using logical arguments to show that the property cannot exist in the graph. It is also helpful to use visual aids, such as the given graph, to assist in the analysis.