MHB How to show a graph contains no Hamilton cycles?

Click For Summary
SUMMARY

This discussion focuses on proving that a specific graph does not contain Hamilton cycles by analyzing vertex degrees and potential routes. The vertices a, k, e, and o, each with a degree of 2, necessitate certain edges to be included in any cycle. The user explored all possible routes starting from vertex b, demonstrating that each route results in a cycle while leaving some vertices disconnected. The conversation also touches on the efficiency of various algorithms for proving the absence of Hamilton cycles.

PREREQUISITES
  • Understanding of graph theory concepts, specifically Hamiltonian cycles
  • Familiarity with vertex degree and its implications in graph connectivity
  • Knowledge of algorithmic approaches to graph traversal
  • Experience with proof techniques in combinatorial mathematics
NEXT STEPS
  • Research algorithms for detecting Hamiltonian cycles in graphs
  • Study the properties of vertex degrees in relation to cycle formation
  • Explore combinatorial proof techniques for graph theory
  • Examine case studies of graphs with known Hamiltonian properties
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory or algorithm design, particularly those interested in Hamiltonian cycles and proof strategies.

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