Demonstrations for Discrete Mathematics
Characterization → Efficient Decision Procedure → Efficient Algorithm
Compare Eulerian Circuit and Hamiltonian Cycle: two graph problems whose definitions differ by a few words, yet whose computational behavior is dramatically different.
Section 1
Every edge exactly once
Ready to inspect edges.
Every vertex exactly once
Ready to search vertices.
Section 2
A connected undirected graph has an Eulerian circuit if and only if every vertex has even degree.
Section 3
There are useful necessary conditions and useful sufficient conditions, but no similarly simple efficiently checkable necessary and sufficient characterization is known that solves the general problem in polynomial time.
Hamiltonian Cycle is NP-complete. The backtracking solver here is an educational visualization, not a claim about the best possible Hamiltonian algorithm.
Section 4
Section 5
Similar looking problem statements do not imply similar computational complexity.
The Eulerian side is driven by structural checks. The Hamiltonian side can be pulled into many alternative vertex orders before it can rule a graph out.