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 cycle visiting every vertex once, with only the start repeated to close it (at least three vertices in a simple graph).

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, a classification developed in the later complexity material. This lesson does not prove a general runtime lower bound.

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): for a finite simple undirected graph on $n \ge 3$ vertices, 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. Distinguish a polynomial-time algorithm from an NP-completeness reduction. NP-completeness is not itself an unconditional proof that no polynomial-time algorithm exists.

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 closed trail with 10 edges and 11 listed vertex occurrences; vertices may repeat.

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$. Adding a parallel edge between two vertices changes the model to a multigraph and leaves two odd vertices, permitting an open Euler trail. It is not an allowed new edge in simple K4, where all vertex pairs are already adjacent.

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 cyclic Gray code listing every length-n bit string once, with the last and first also differing in one bit, gives a Hamilton cycle on $Q_n$ for $n \ge 2$. 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 to the workshop model

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

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

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Edge coverage, vertex coverage and empty conventions

For an undirected graph with at least one edge, all non-isolated vertices must lie in one component for an Euler trail to cover every edge. Zero odd degrees yields a closed trail; two yields an open trail. With no edges the lab reports empty, leaving a zero-length convention explicit.

A Hamilton cycle visits each vertex exactly once except its closing repetition, and requires n≥3 under the simple-graph convention. The two-triangles-with-shared- vertex example is Eulerian but not Hamiltonian. A Gray-code ordering gives a Hamilton path only if every cube vertex appears once; a cycle additionally needs the last and first words to differ in one bit. Transfer: P16.

After your attempt use practice feedback and model contracts to check the argument.