Hamiltonian Graph Examples

Graph Theory · Axiom Academy

EXAMPLE Hamiltonian Graph Examples Master Hamiltonian cycles, proofs, theorems, and comparisons Graph G with 5 vertices and 7 edges Excellent work! You've mastered Hamiltonian graph analysis. Here's what we learned: Finding Hamiltonian Cycles: Systematically construct paths visiting each vertex exactly once, then verify all edges exist in the graph. Proving Non-Hamiltonian: Use structural properties like cut vertices, degree sequences, or vertex connectivity to show no Hamiltonian cycle can exist. Dirac's Theorem: If every vertex has degree ≥ n/2 (where n ≥ 3), the graph is guaranteed to be Hamiltonian. This is a sufficient but not necessary condition. Ore's Theorem: If deg(u) + deg(v) ≥ n for all non-adjacent vertices u and v, then G is Hamiltonian. This generalizes Dirac's theorem. Eulerian vs Hamiltonian: Eulerian graphs traverse every edge once (solvable in polynomial time with clear necessary/sufficient conditions), while Hamiltonian graphs visit every vertex once (NP-complete problem with no simple necessary/sufficient condition). Important Distinction: A graph can be Hamiltonian but not Eulerian, Eulerian but not Hamiltonian, both, or neither. The properties are independent. Practice applying Dirac's and Ore's theorems to quickly identify Hamiltonian graphs, and remember that proving non-Hamiltonian requires structural analysis or exhaustive search!

This is the written version of the interactive lesson above. See the full Graph Theory course.