What is the difference between Eulerian and Hamiltonian paths in graph theory?

**Eulerian vs Hamiltonian — The Key Distinction:** | Property | Eulerian | Hamiltonian | |---|---|---| | Covers | Every **edge** once | Every **vertex** once | | Easy to check? | Yes (simple conditions) | No (NP-complete in general) | | Named after | Euler | Hamilton | **Eulerian Circuit Conditions (for undirected graphs):** - **All vertices must have even degree** (necessary and sufficient, assuming the graph is connected with at least one edge). - An Eulerian **path** (not circuit) exists iff exactly 0 or 2 vertices have odd degree. **Hamiltonian Cycle — Why It's Hard:** There is no simple necessary and sufficient condition. Dirac's theorem gives a sufficient condition: if every vertex has degree $\geq n/2$, the graph has a Hamiltonian cycle. But many Hamiltonian graphs don't meet this condition. The Hamiltonian path problem is NP-complete, meaning no efficient algorithm is known for all cases. **Knight's Tour:** This is a Hamiltonian path problem (the knight visits every square/vertex exactly once), not Eulerian. **Fleury's Algorithm for Eulerian Circuits:** 1. Start at any vertex. 2. Traverse edges, but never use a **bridge** (an edge whose removal disconnects the remaining graph) unless absolutely necessary. 3. Mark used edges and continue until all edges are used. **Example:** A graph with vertices $A, B, C, D$ and edges $AB, BC, CD, DA, AC$. All vertices have degree 3 $\Rightarrow$ not Eulerian. But if we add $BD$, all vertices have degree 4 $\Rightarrow$ Eulerian circuit exists.