1
Euler is decided by the degrees
One pass over the vertices. Even degrees and connectivity are necessary and sufficient, which is unusually clean.
Lesson · Graphs and Trees · Traversal
Euler and Hamilton Paths
An Euler circuit uses every edge once and exists exactly when the graph is connected with all degrees even. A Hamilton circuit visits every vertex once and has no such criterion — deciding it is NP-complete.
EULER every EDGE once criterion: connected, all degrees even
Euler PATH: exactly two odd-degree vertices
HAMILTON every VERTEX once NO simple criterion — NP-complete
The problems look alike. They are not.
One easy, one hard
Core ideas
What this lesson establishes
Two similar-sounding questions with completely different answers, and the contrast is the point of the lesson.
2
The degree condition has an obvious reason
Every visit to a vertex uses two edge-ends, one in and one out. So a circuit requires every degree even.
3
Hamilton has no such criterion
Only sufficient conditions (Dirac, Ore) and no characterisation. Deciding it is NP-complete, which Algorithms and Complexity defines.
The material
Euler and Hamilton
Both definitions, Euler's theorem with its proof, and the contrast.
Definition · Euler path and circuit
An Euler path uses every edge of the graph exactly once. An Euler circuit is an Euler path that returns to its starting vertex.
Theorem · Euler's theorem
A connected graph has an Euler circuit if and only if every vertex has even degree. It has an Euler path but no circuit if and only if exactly two vertices have odd degree, and any such path starts at one and ends at the other.
Necessity. Every time the circuit enters a vertex it leaves again, using two edges at that vertex; the start and end are the same vertex, so its first and last edges pair up too. Every edge is used exactly once, so every degree is even.
Sufficiency. Suppose the graph is connected with all degrees even. Start anywhere and walk, never repeating an edge. Even degrees mean that whenever you enter a vertex other than the start there is an unused edge to leave by, so the walk can only get stuck at the start — producing a circuit.
If that circuit misses some edges, connectivity gives a vertex v on it with unused edges. The unused edges still form a graph of even degrees, so the same argument gives a second circuit through v, which can be spliced into the first. Repeating exhausts the edges.
□
That is a complete criterion and an algorithm: check the degrees, and the splicing argument (Hierholzer's algorithm) constructs the circuit in linear time.
Example · The bridges of Königsberg
Four land masses joined by seven bridges. The question — can one walk crossing every bridge exactly once? — is whether an Euler path exists. The four vertices have degrees 5, 3, 3 and 3: four vertices of odd degree, and a path allows at most two. No such walk exists, and Euler proved it in 1736.
Notice how little the argument needs. The geometry, the distances and the layout were all discarded; only the degrees mattered. That abstraction is the founding move of graph theory.
Hamilton
Definition · Hamilton path and circuit
A Hamilton path visits every vertex exactly once. A Hamilton circuit is a Hamilton path returning to its start.
There is no known criterion. Some sufficient conditions exist:
Theorem · Dirac's theorem
If n ≥ 3 and every vertex has degree at least n/2, the graph has a Hamilton circuit.
Theorem · Ore's theorem
If n ≥ 3 and deg(u) + deg(v) ≥ n for every pair of non-adjacent u, v, the graph has a Hamilton circuit.
Both are sufficient and neither is necessary: Cₙ has a Hamilton circuit and every degree 2, far below n/2. There is no known condition that is both.
Theorem · Hamiltonicity is NP-complete
Deciding whether a graph has a Hamilton circuit is NP-complete. No polynomial-time algorithm is known, and one would imply P = NP.
Euler Hamilton
covers every EDGE once every VERTEX once
criterion degrees all even none known
deciding it linear time NP-complete
constructing it Hierholzer, linear exponential in general
This table is the lesson. Two questions that a reader would expect to be of similar difficulty are on opposite sides of the sharpest boundary in computer science, and nothing in the statements reveals which is which.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Deciding both questions
Euler is a degree count. Hamilton is a search.
1
For Euler, check connectivity and count odd degrees
Zero odd degrees gives a circuit; exactly two give a path; anything else gives neither.
2
Construct the Euler circuit by splicing
Walk until stuck, then find a vertex with unused edges and splice in a second circuit. That is Hierholzer's algorithm.
3
For Hamilton, check the sufficient conditions
Dirac and Ore. If either holds, a circuit exists. If neither holds, nothing follows.
4
Otherwise search, and expect it to be slow
Backtracking over orderings. For n beyond about 20 this is impractical, and no better general method is known.
Euler and Hamilton
Score 0 / 0Choose the answer you can justify.
Königsberg, and a fix
Four land masses A, B, C, D with seven bridges.
degrees: A: 5 B: 3 C: 3 D: 3
odd-degree vertices: all four.
An Euler PATH allows at most 2; a CIRCUIT allows 0.
⟹ neither exists. No such walk is possible.
ADD ONE BRIDGE between B and C:
degrees: A: 5 B: 4 C: 4 D: 3
now exactly two odd (A and D) ⟹ an Euler PATH exists,
and it must start at A and end at D.
ADD A SECOND, between A and D:
degrees: A: 6 B: 4 C: 4 D: 4
all even ⟹ an Euler CIRCUIT exists, from anywhere.
The bridges added were chosen to fix parity, and any bridge joining two odd-degree vertices would have done. That is the practical form of the theorem: the obstruction is parity, and parity is what you repair.
Common mistakes
1
Confusing the two problemsEuler covers edges; Hamilton covers vertices. The difficulty is completely different and nothing in the wording signals it.
2
Applying Dirac's condition in reverseIt is sufficient, not necessary. Cₙ has degree 2 everywhere and a Hamilton circuit.
3
Forgetting connectivity in Euler's criterionTwo disjoint even-degree cycles have all degrees even and no Euler circuit. The edges must lie in one component.
Check your understanding
✓
Finish when you can settle Euler in one pass and say why Hamilton is different.
For a graph of your own, decide the Euler question by counting degrees, then attempt Hamilton by hand and notice what changes: one is a check, the other is a search.
Note: The travelling salesman problem is Hamilton with weights: find the cheapest Hamilton circuit. It is the canonical hard optimisation problem, and “P, NP and NP-Completeness” in Algorithms and Complexity places it precisely.