Skip to main content

Euler Tours, Hamilton Paths, and Edge vs Vertex Constraints

What This Concept Is​

Euler and Hamilton problems sound similar but govern very different objects:

  • Euler trail: a walk that uses every edge exactly once.
  • Euler circuit / tour: a closed Euler trail (starts and ends at the same vertex).
  • Hamilton path: a path that visits every vertex exactly once.
  • Hamilton cycle: a closed Hamilton path.

That one-letter change -- edges versus vertices -- produces a world of difference in difficulty. Euler questions are heavily controlled by degree parity, which yields a clean if-and-only-if characterization and a polynomial-time algorithm (Hierholzer's). Hamilton questions have no such clean criterion: deciding whether a Hamilton cycle exists is NP-complete for general graphs, and no efficient algorithm is known (nor expected).

Euler's theorem (1736, Königsberg bridges). A connected graph has an Euler circuit $\iff$ every vertex has even degree. It has an Euler trail (not closed) $\iff$ exactly two vertices have odd degree (the trail starts at one odd vertex and ends at the other).

The proof idea: every time you enter a vertex along an unused edge, you must leave along another unused edge. That pairs incident edges locally; only even degree allows a closed traversal that uses all edges. The odd-trail case corresponds to the two endpoints being the two "unpaired" vertices.

Hamilton theorems are weaker. We have sufficient conditions (Dirac's, Ore's) but no known efficient necessary-and-sufficient characterization:

  • Dirac (1952): if every vertex in a simple graph on $n \ge 3$ vertices has degree $\ge n/2$, then the graph has a Hamilton cycle.
  • Ore (1960): if $\deg(u) + \deg(v) \ge n$ for every non-adjacent pair $u, v$, then Hamilton cycle exists.

These conditions are sharp but far from tight -- many Hamiltonian graphs violate them.

Why It Matters Here​

This distinction is a perfect example of why good graph reasoning starts with the right invariant. If you use vertex-based intuition on an edge-coverage problem, you miss the structure entirely. Parity arguments solve Euler questions in seconds; the same arguments reveal almost nothing about Hamilton questions.

The contrast also previews the P vs NP boundary you meet in Semester 2. Euler trails sit firmly in P; Hamilton cycles are NP-complete, and their hardness drives lower-bound thinking in algorithm analysis. Knowing which side of the P / NP boundary a graph property lies on is often more important than knowing its exact algorithm.

Concrete Examples​

Example 1: Königsberg bridges. The historical problem: seven bridges connect four landmasses in Königsberg (now Kaliningrad). Is there a walk that crosses each bridge exactly once?

Graph model: one vertex per landmass, one edge per bridge. The four vertices have degrees $3, 3, 3, 5$ -- all odd. By Euler's theorem, no Euler trail exists (requires $\le 2$ odd-degree vertices). Hence no single-pass crossing is possible.

This was the birth of graph theory: Euler (1736) proved impossibility without exhaustive search, turning a concrete puzzle into the first theorem of the field.

Example 2: Euler circuit in a complete graph. Does $K_5$ have an Euler circuit?

Every vertex of $K_5$ has degree $4$ (even). Graph is connected. By Euler's theorem, yes. Hierholzer's algorithm constructs one in linear time: start at any vertex, follow unused edges greedily; if you get stuck (must be at the start), splice in detours from vertices that still have unused edges. For $K_5$ (10 edges), the output is a length-10 cycle of vertices hitting each edge once.

Does $K_4$ have an Euler circuit? Each vertex has degree $3$ (odd). By Euler, no -- but $K_4$ does admit an Euler trail? No again: it has $4$ odd-degree vertices, not just $2$. You must add a "virtual edge" between two odd-degree vertices to make an Euler trail possible.

Example 3: Hamilton cycle in a cube graph. The graph $Q_3$ (cube, $8$ vertices indexed by binary strings of length $3$, edges between strings differing in one bit).

All vertices have degree $3$. Dirac's threshold is $n/2 = 4$, so Dirac does not apply. Yet $Q_3$ is Hamiltonian; a Gray code (binary strings ordered so consecutive entries differ in one bit) is precisely a Hamilton cycle on $Q_n$. Example for $n=3$: $000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$.

This illustrates that Dirac/Ore are sufficient but not necessary: many Hamiltonian graphs fail their hypotheses.

Common Confusion / Misconceptions​

  • Euler and Hamilton are basically the same. No. Euler asks about edge coverage; Hamilton asks about vertex coverage. Very different computational complexity, very different invariants.
  • Using degree parity for Hamilton. Hamilton cycles have no simple parity characterization. Degree-based sufficient conditions exist (Dirac/Ore), but no if-and-only-if based on local information is known.
  • Euler circuit requires even number of edges. No -- an Euler circuit requires each vertex to have even degree, not an even total edge count. $K_5$ has $10$ edges and $5$ vertices of even degree; $C_5$ has $5$ edges and also works.
  • Hamilton cycle implies Hamilton path, and vice versa. Only the first direction: a Hamilton cycle, with any edge removed, becomes a Hamilton path. The reverse requires an extra edge closing the path, which may not exist.
  • All planar graphs are Hamiltonian. False. Even $3$-connected planar graphs need not be Hamiltonian (Tutte 1946 counterexample).

How To Use It​

When facing a traversal question, ask first:

  1. Am I required to use every edge (Euler) or every vertex (Hamilton)? Read the problem slowly.
  2. Is the graph connected enough for the question even to make sense? (Disconnected graphs with $> 1$ edge-containing component cannot have Euler trails.)
  3. Does parity control the situation (Euler) or is this a harder global-structure question (Hamilton)?
  4. If Euler: count odd-degree vertices. $0 \to$ Euler circuit exists; $2 \to$ Euler trail exists; otherwise, neither.
  5. If Hamilton: try sufficient conditions (Dirac, Ore). If the graph satisfies one, done. If not, the problem is likely computationally hard.
  6. For Hamilton in special graph families (planar, bipartite, small $n$): specialized theorems or brute-force may work; do not expect a universal efficient method.
  7. Consider why the distinction arises: local pairing (Euler) is enforceable by counting at each vertex; global routing (Hamilton) requires exponential-in-$n$ search in the worst case.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: Hierholzer's algorithm for Euler tours ($O(m)$) and Chinese Postman Problem (find shortest closed walk using all edges) rely on Euler theory. Hamilton cycle's NP-completeness is a canonical reduction target; TSP (traveling salesman) is its metric version.
  • Semester 3 data structures: circuit-detection routines in graph algorithms use Euler-trail logic for certain special classes (e.g., DeBruijn graphs, where Euler circuits enumerate all $n$-grams in a sequence).
  • Semester 4 databases / bioinformatics (adjacent): DNA assembly uses De Bruijn graphs and finds Eulerian paths to reconstruct sequences from $k$-mer overlaps.
  • Semester 5 OS: Euler-tour decompositions underlie fast LCA queries and Euler-tour trees for dynamic connectivity.
  • Semester 6 distributed systems: token-ring protocols traverse Hamilton cycles; deadlock-free resource ordering uses Hamilton-like orderings on resource types.
  • Semester 7 architecture: build-order validation uses Euler-style edge coverage when every dependency must be exercised; deployment-order planning uses Hamilton-style vertex coverage when every service must be deployed exactly once.

Check Yourself​

  1. Why can parity decide Euler structure? Give the local pairing argument in one paragraph.
  2. Why is Hamilton structure usually harder to certify? Relate to P vs NP.
  3. Can a graph have a Hamilton cycle but no Euler circuit? Give an example. Can it have the reverse?
  4. State Dirac's theorem and give a graph where it applies. Find a graph that is Hamiltonian but violates Dirac.
  5. Why do the Königsberg bridges have no Euler trail?
  6. What is the time complexity of the best known algorithm for deciding Hamilton cycle existence in a general graph?

Mini Drill or Application​

For each graph (draw your own or use standard families), decide whether it has:

  1. an Euler path
  2. an Euler circuit
  3. a Hamilton path
  4. a Hamilton cycle

Explain which invariants support each answer. Try:

  • $K_5$ (complete graph on $5$): Euler circuit? Hamilton cycle?
  • $K_{3,3}$ (complete bipartite): Euler circuit? Hamilton cycle?
  • $C_6$ (cycle on $6$): Euler circuit? Hamilton cycle?
  • $P_4$ (path on $4$): Euler trail? Hamilton path?
  • The Petersen graph: Hamilton cycle? (Answer: no -- famous counterexample.)

Read This Only If Stuck​