How to show a graph contains no Hamilton cycles?

Click For Summary

Discussion Overview

The discussion revolves around the problem of demonstrating that a specific graph does not contain any Hamiltonian cycles. Participants explore methods for proving the absence of such cycles, including the examination of vertex degrees and potential routes within the graph.

Discussion Character

  • Exploratory, Technical explanation, Homework-related

Main Points Raised

  • One participant describes a method involving the identification of edges that must be included in the cycle due to certain vertices having a degree of 2, and lists possible routes starting from a specific vertex.
  • Another participant suggests that there are several algorithms available for addressing the problem of proving the absence of Hamiltonian cycles and provides links to additional resources.
  • There is an acknowledgment of the resources shared, indicating interest in further reading.

Areas of Agreement / Disagreement

Participants appear to agree on the need for efficient methods to demonstrate the absence of Hamiltonian cycles, but no consensus is reached on a specific procedure or method.

Contextual Notes

The discussion does not resolve the question of the most efficient method for proving the absence of Hamiltonian cycles, and the proposed algorithms are not evaluated for their effectiveness.

Who May Find This Useful

Readers interested in graph theory, particularly those studying Hamiltonian cycles and methods for proving their absence, may find this discussion relevant.

annie122
Messages
51
Reaction score
0
Here is the graph in question:
a1642v.jpg


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?
 
Physics news on Phys.org
Yuuki said:
Here is the graph in question:
a1642v.jpg


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<<.
 
Thank you for the reply for this thread and the other one.
I'll definitely read the PDF.
 
Yuuki said:
Thank you for the reply for this thread and the other one.
I'll definitely read the PDF.

You are welcome. (Handshake)
 

Similar threads

MHB Is HSC NP-Complete in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Another tree-related graph theory proof
  • · Replies 1 ·
Replies
1
Views
2K
MHB A Subset of a Graph with No Perfect Matching
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Does G with all its degrees at least three contain a cycle with a chord?
  • · Replies 3 ·
Replies
3
Views
4K
MHB Finding a Minimal Vertex Cover & Max Sets for a Graph
  • · Replies 2 ·
Replies
2
Views
2K
MHB Some basic questions on Graph theory
  • · Replies 2 ·
Replies
2
Views
2K
MHB Graph theory proof related to trees
  • · Replies 1 ·
Replies
1
Views
2K