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, using degree conditions | No; the general decision problem is NP-complete | **Eulerian conditions for a connected undirected graph:** - An Eulerian circuit exists exactly when every vertex has even degree. - An Eulerian path but no circuit exists exactly when two vertices have odd degree. **Hamiltonian cycles:** There is no comparably simple necessary-and-sufficient degree test. Dirac's theorem gives a useful sufficient condition: a graph with $n\geq3$ vertices is Hamiltonian if every vertex has degree at least $n/2$, but many Hamiltonian graphs do not satisfy that condition. **Knight's Tour:** This is a Hamiltonian path problem because each square is a vertex and the knight must visit every square once. **Fleury's algorithm:** Start at a vertex of odd degree if there are exactly two; otherwise start anywhere. At each step avoid a bridge of the remaining graph unless it is the only available edge. Continue until every edge has been used. **Correct example:** The graph with edges $AB,BC,CD,DA,AC$ has degrees $3,2,3,2$. It has an Eulerian path because exactly two vertices are odd, but no Eulerian circuit. The simple cycle with edges $AB,BC,CD,DA$ has degree $2$ at every vertex and therefore has an Eulerian circuit.