Eulerian and Hamiltonian Summary

Graph Theory · Axiom Academy

SUMMARY Eulerian and Hamiltonian Paths Let's review the key contrasts between these two fundamental path types in graph theory. Definition: A path that uses every edge exactly once Circuit vs Path: Circuit returns to start; path does not require this Easy to Check: Euler's theorem provides simple degree conditions Polynomial Time: Can find Eulerian paths efficiently (O(E) time) Definition: A path that visits every vertex exactly once Circuit vs Path: Circuit forms a cycle; path does not close the loop Hard to Check: No simple characterization exists NP-Complete: No known polynomial-time algorithm to find or verify Hamiltonian Sufficient Conditions (The Bad News) No simple necessary and sufficient condition exists, but we have useful sufficient conditions: Dirac's Theorem: If n ≥ 3 and every vertex has degree ≥ n/2, then the graph is Hamiltonian Ore's Theorem: If n ≥ 3 and deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u and v, then the graph is Hamiltonian Limitation: These are sufficient but not necessary—many Hamiltonian graphs don't satisfy these conditions The Fundamental Contrast: Easy vs Hard Eulerian Decision: Polynomial time—just count vertex degrees Hamiltonian Decision: NP-complete—no efficient algorithm known Eulerian Construction: Hierholzer's algorithm runs in O(E) time Hamiltonian Construction: Requires exponential backtracking in worst case

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