Eulerian and Hamiltonian Graphs

Eulerian graphs admit a closed walk traversing every edge exactly once; Hamiltonian graphs admit a cycle visiting every vertex exactly once. Euler's condition (connectedness + all-even degrees) is clean and efficiently checkable; Hamiltonicity has no such simple characterization and is NP-complete. Foundational results from Euler (1736) and Hamilton (1857), central to graph theory, combinatorial optimization, and routing.

An Eulerian circuit is a closed walk in a graph that uses every edge exactly once; a graph possessing one is called Eulerian. A Hamiltonian cycle is a cycle that passes through every vertex exactly once; a graph possessing one is Hamiltonian. Though superficially parallel (edges vs. vertices), these two notions are profoundly asymmetric in difficulty: Euler gave a complete, locally-checkable degree criterion in 1736 while solving the Königsberg Bridges Problem — the historical birth of graph theory — whereas no efficient characterization of Hamiltonicity is known, and deciding it is NP-complete. The surprising fact is that a question about edges (seemingly "harder," more numerous) is easy, while a question about vertices is among the hardest problems in computer science.

The Core Insight

Eulerian = local condition (degrees) ⟹ global structure. Whether you can trace every edge without lifting your pen depends only on counting edges at each vertex: every time a walk enters a vertex it must leave, pairing up edges, so all interior degrees must be even. This local-to-global bridge makes Euler problems tractable. Hamiltonian = irreducibly global. Visiting each vertex once cannot be certified by any purely local count; degree conditions only give sufficient (never necessary) guarantees, and the property resists decomposition. This is the conceptual root of its computational hardness.

Formal Statement

Walks, Trails, Paths, Circuits, Cycles

Let $G = (V, E)$ be a graph.

A walk is an alternating sequence $v_{0} e_{1} v_{1} e_{2} \dots e_{k} v_{k}$ of vertices and edges with $e_{i} = {v_{i - 1}, v_{i}}$ .
A trail is a walk with no repeated edge.
A path is a walk with no repeated vertex.
A circuit (closed trail) is a trail with $v_{0} = v_{k}$ .
A cycle is a closed path (no repeated vertex except $v_{0} = v_{k}$ ), with $k \geq 3$ in simple graphs.

An Eulerian circuit is a circuit containing every edge of $G$ ; an Eulerian trail is an (open) trail containing every edge. A Hamiltonian cycle is a cycle containing every vertex of $G$ ; a Hamiltonian path contains every vertex without necessarily closing.

Degree and Handshake Identity

The degree $de g (v)$ is the number of edge-ends incident to $v$ (loops count twice). The handshake lemma gives:

v \in V \sum de g (v) = 2∣ E ∣

⟳each edge contributes exactly two endpoints to the total degree sum, so the sum is even and equals twice the edge count.

Euler's Theorem, 1736

A connected graph $G$ (with at least one edge) has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian trail (open) if and only if exactly two vertices have odd degree; the trail begins at one and ends at the other.

G Eulerian ⟺ G connected (on edges) \land \forall v de g (v) \equiv 0 (mod 2)

⟳necessity from the entering/leaving pairing argument; sufficiency by the constructive Hierholzer cycle-splicing procedure.

Directed Euler Criterion

A connected digraph $D$ has a directed Eulerian circuit iff it is balanced — for every vertex, in-degree equals out-degree:

D Eulerian ⟺ strongly connected (on edges) \land \forall v d^{+} (v) = d^{-} (v)

⟳each pass through a vertex consumes one incoming and one outgoing arc, so they must match; connectivity ensures a single circuit covers all arcs.

Dirac's Theorem, 1952

If $G$ is a simple graph on $n \geq 3$ vertices and every vertex satisfies $de g (v) \geq n /2$ , then $G$ is Hamiltonian.

δ (G) \geq \frac{n}{2} ⟹ G Hamiltonian

⟳assume a longest path; high minimum degree forces its endpoints to have a common rotation creating a cycle through all path vertices, then connectivity forces the cycle to be spanning.

Ore's Theorem, 1960

If $G$ is simple on $n \geq 3$ vertices and for every pair of non-adjacent vertices $u, v$ ,

de g (u) + de g (v) \geq n ⟹ G Hamiltonian

⟳same longest-path rotation argument as Dirac, but the degree budget is shared between the two path endpoints, generalizing

δ \geq n /2

Bondy–Chvátal Closure, 1976

The closure $cl (G)$ is obtained by repeatedly adding an edge between any non-adjacent pair $u, v$ with $de g (u) + de g (v) \geq n$ . Then $G$ is Hamiltonian iff $cl (G)$ is Hamiltonian; in particular if $cl (G) = K_{n}$ , $G$ is Hamiltonian.

G Hamiltonian ⟺ cl (G) Hamiltonian

⟳adding an edge whose endpoints satisfy the degree sum condition cannot change Hamiltonicity, by an exchange/rotation argument; iterate until stable.

Why It Holds / Derivation

Euler's Theorem — Necessity

Claim: If

G

is Eulerian, every degree is even.

Let $W = v_{0} e_{1} v_{1} \dots e_{m} v_{0}$ be an Eulerian circuit traversing all $m = ∣ E ∣$ edges exactly once.
Fix a vertex $v$ . Each occurrence of $v$ as an interior vertex $v_{i}$ pairs the incoming edge $e_{i}$ with the outgoing edge $e_{i + 1}$ — two distinct incident edges consumed together.
Because $W$ is closed, the start/end vertex $v_{0}$ is also balanced: the very first edge $e_{1}$ pairs with the very last edge $e_{m}$ .
Since every edge incident to $v$ appears exactly once in $W$ and they group into entering/leaving pairs, $de g (v)$ is even. $■$

Euler's Theorem — Sufficiency via Hierholzer

Claim: Connected + all-even-degree ⟹ Eulerian circuit, constructively.

Start at any vertex $v_{0}$ . Greedily walk along unused edges; because every degree is even, whenever you enter a vertex you can always leave (an odd number of used edges would be needed to get stuck). So the walk can only terminate by returning to $v_{0}$ , producing a closed circuit $C_{1}$ .
If $C_{1}$ uses all edges, done.
Otherwise, by connectivity some vertex $w$ on $C_{1}$ has unused incident edges. Restricting to unused edges, $w$ still has even degree, so repeat step 1 from $w$ to obtain another closed circuit $C_{2}$ .
Splice $C_{2}$ into $C_{1}$ at $w$ (traverse $C_{1}$ up to $w$ , detour around $C_{2}$ , continue $C_{1}$ ). The result is a longer closed circuit.
Iterate. Each splice adds edges; the edge set is finite, so eventually all edges are absorbed into a single Eulerian circuit. Runtime is $O (∣ E ∣)$ . $■$

Ore's Theorem

Suppose, for contradiction, that $G$ satisfies the Ore condition $de g (u) + de g (v) \geq n$ for all non-adjacent $u, v$ but is not Hamiltonian. Add edges (keeping the condition true — adding edges only raises degrees) until $G$ is maximally non-Hamiltonian: one more edge creates a Hamiltonian cycle.
Then $G$ has a Hamiltonian path $x_{1} x_{2} \dots x_{n}$ (adding the missing edge $x_{1} x_{n}$ would complete a cycle, so the path spans all vertices).
Consider the index sets $S = {i : x_{1} x_{i + 1} \in E}$ and $T = {i : x_{i} x_{n} \in E}$ , both subsets of ${1, \dots, n - 1}$ . Then $∣ S ∣ = de g (x_{1})$ and $∣ T ∣ = de g (x_{n})$ .
Since $x_{1}, x_{n}$ are non-adjacent, $de g (x_{1}) + de g (x_{n}) \geq n$ , so $∣ S ∣ + ∣ T ∣ \geq n > n - 1$ . By pigeonhole, $S \cap T \neq = \emptyset$ : there is an index $i$ with $x_{1} x_{i + 1} \in E$ and $x_{i} x_{n} \in E$ .
This yields the cycle $x_{1} x_{2} \dots x_{i} x_{n} x_{n - 1} \dots x_{i + 1} x_{1}$ through all $n$ vertices — a Hamiltonian cycle. Contradiction. $■$

Leonhard Euler | 1707–1783

The most prolific mathematician in history, Euler launched graph theory with his 1736 paper Solutio problematis ad geometriam situs pertinentis ("The solution of a problem relating to the geometry of position"). Asked whether one could cross all seven bridges of Königsberg exactly once and return, Euler abstracted the river-and-land map into what we now call a multigraph and proved it impossible by the parity-of-degrees argument. He thereby invented geometry of position (topology/combinatorics) — geometry where distances and angles are irrelevant and only connectivity matters. The very idea that a counting argument on incidences could settle a path-existence question is the seed of all modern graph theory.

Building Intuition

Think of an Eulerian circuit as a single closed loop of thread that covers every edge. At each vertex the thread passes through: in and out, in and out. If a vertex had an odd number of strands meeting it, the thread would have to start or stop there — impossible for a closed loop. So "all degrees even" is just "every vertex is a clean pass-through point."

For the open trail version, exactly two vertices are allowed to be odd: those are precisely the loose ends of the thread — the start and the finish. Zero or two odd vertices: never an odd number, because [1] forces the count of odd-degree vertices to be even.

Hamiltonicity feels deceptively similar but is fundamentally different: you are choosing a subset structure (one big cycle through points) where local pass-through logic gives no leverage — you cannot certify success by looking at any bounded neighborhood. This is why Euler hands you a yes/no answer in linear time while Hamilton hands you a needle in an exponential haystack.

Königsberg multigraph (Eulerian-impossible) vs. a graph with an Eulerian circuit

Worked Examples

Eulerian trail in a small graph

Given: Graph on vertices

{A, B, C, D, E}

with edges

A B, B C, C D, D A

(a 4-cycle) plus

A C

and

C E, E B

. Step 1 — Compute degrees:

$de g (A) = ∣ {A B, D A, A C} ∣ = 3$
$de g (B) = ∣ {A B, B C, E B} ∣ = 3$
$de g (C) = ∣ {B C, C D, A C, C E} ∣ = 4$
$de g (D) = ∣ {C D, D A} ∣ = 2$
$de g (E) = ∣ {C E, E B} ∣ = 2$

Step 2 — Count odd-degree vertices:

A

and

B

are odd; exactly two. So no Eulerian circuit, but an Eulerian trail exists, starting at

A

, ending at

B

(or vice versa). Step 3 — Construct the trail by Hierholzer/Fleury from

A

A \to C \to D \to A \to B \to C \to E \to B

Edges used in order:

A C, C D, D A, A B, B C, C E, E B

— all 7 edges, each once.

Eulerian trail: A C D A B C E B (open, A \to B)

Applying Dirac & Ore

Given: Simple graph

G

n = 6

vertices where every vertex has degree exactly

3

. Step 1 — Dirac test: Need

δ (G) \geq n /2 = 3

. Here

δ = 3 \geq 3

. ✓ Dirac satisfied ⟹ Hamiltonian.

Concretely, the prism graph $K_{3} \times K_{2}$ (two triangles $123$ and $456$ joined by edges $14, 25, 36$ ) is 3-regular on 6 vertices. A Hamiltonian cycle:

1 \to 2 \to 3 \to 6 \to 5 \to 4 \to 1.

Step 2 — Contrast with Ore on a borderline graph: Take

n = 5

, two non-adjacent vertices

u, v

with

de g (u) = de g (v) = 2

. Then

de g (u) + de g (v) = 4 < 5 = n

, so Ore is not satisfied — the theorem gives no guarantee (the graph may or may not be Hamiltonian; the test is only sufficient).

Prism K_{3} \times K_{2} is Hamiltonian; cycle 1236541

Common Misconceptions

Dirac and Ore are SUFFICIENT, never NECESSARY. Failing the degree condition tells you nothing. The cycle

C_{n}

(a simple

n

-gon) is obviously Hamiltonian yet every vertex has degree only

2 ≪ n /2

for large

n

. Never conclude "not Hamiltonian" from a degree condition. Eulerian ≠ Hamiltonian. They are independent properties. A graph can be Eulerian but not Hamiltonian, Hamiltonian but not Eulerian, both, or neither. "Eulerian" sometimes means circuit, sometimes trail — authors differ. Many texts call a graph with an open Eulerian trail "semi-Eulerian." Always check the definition in use. Connectivity is required. Even if all degrees are even, a disconnected graph (with edges in more than one component) has no Eulerian circuit. The criterion is "connected on its non-isolated vertices AND all even." Eulerian but NOT Hamiltonian: Take two triangles sharing a single common vertex

v

(a "bowtie"): vertices

{v, a, b, c, d}

, edges

v a, ab, b v, v c, c d, d v

. Every vertex has even degree (

de g v = 4

, others

= 2

), and it is connected, so it is Eulerian. But it has no Hamiltonian cycle: any cycle through all five vertices would have to pass through the cut-vertex

v

twice (to enter and leave each triangle), which a cycle cannot do. Eulerian ✓, Hamiltonian ✗. Hamiltonian but NOT Eulerian: The complete graph

K_{4}

has a Hamiltonian cycle (

12341

) but every vertex has degree

3

(odd), so it has no Eulerian circuit. Hamiltonian ✓, Eulerian ✗.

Connections

Eulerian and Hamiltonian problems sit at a crossroads of several areas:

Königsberg Bridge Problem — the historical and conceptual origin of the Eulerian criterion.
Graph Connectivity — both notions presuppose connectivity; cut-vertices obstruct Hamiltonicity.
Traveling Salesman Problem — the weighted optimization version of finding a Hamiltonian cycle of minimum total cost; Hamiltonicity is its feasibility core.
NP-Completeness — HAMILTONIAN CYCLE is one of Karp's 21 NP-complete problems; Euler circuit is in P, dramatizing the P vs. NP boundary.
Chinese Postman Problem — the optimization relative of Eulerian circuits: traverse every edge with least repetition, solved efficiently via Matching Theory.
Planar Graphs — Tait's conjecture linked Hamiltonicity of cubic planar graphs to the Four Color Theorem (later disproved).

Real-World Applications

DNA sequence assembly (de Bruijn graphs). Modern genome assemblers represent overlapping $k$ -mers as edges and reconstruct sequences by finding Eulerian paths in a de Bruijn graph — exploiting the efficiency of the Euler criterion over the intractable Hamiltonian formulation originally used.
Snow-plowing / street sweeping / mail delivery (Chinese Postman). Routing a vehicle down every street with minimum repeated mileage is an Eulerian-circuit augmentation problem solved in polynomial time.
Printed circuit board drilling & CNC tool-path optimization. Visiting every drill hole once with minimum travel is a Hamiltonian / TSP instance.
Logistics & vehicle routing. Delivery tours minimizing distance are weighted Hamiltonian-cycle (TSP) problems; near-optimal heuristics drive billions in shipping decisions.
Network reliability and circuit testing. Eulerian decompositions test that every connection (edge) is exercised exactly once.
Mazes, robotics coverage, and lawn-mowing robots. Edge-covering (Euler) vs. vertex-covering (Hamilton) models map onto exhaustive sweep vs. waypoint-visiting tasks.
Bioinformatics fragment assembly & telecommunications ring design. SONET/SDH self-healing rings are physical Hamiltonian cycles ensuring single-loop redundancy.

Historical Development

1736 — Leonhard Euler solves the Seven Bridges of Königsberg, proving no closed walk crosses every bridge once; founds graph theory and "geometry of position."
1809–1813 — Louis Poinsot studies closed routes touching every point, an early Hamiltonian-flavored question.
1857 — William Rowan Hamilton invents the Icosian Game, asking for a cycle through all 20 vertices of a dodecahedron; the term "Hamiltonian cycle" derives from this puzzle.
1873 — Carl Hierholzer publishes the constructive cycle-splicing proof of Euler's sufficiency (the Hierholzer algorithm), posthumously.
1880 — P. G. Tait conjectures every 3-connected cubic planar graph is Hamiltonian, linking it to the Four Color Theorem (disproved by Tutte, 1946).
1936 — Dénes Kőnig's textbook Theorie der endlichen und unendlichen Graphen, the first systematic graph theory monograph, codifies Euler/Hamilton results.
1952 — Gabriel Dirac proves the minimum-degree sufficient condition $δ \geq n /2$ .
1960 — Øystein Ore generalizes to the degree-sum condition for non-adjacent pairs.
1972 — Richard Karp lists HAMILTONIAN CYCLE among his 21 NP-complete problems, cementing the Euler/Hamilton complexity dichotomy.
1976 — Bondy and Chvátal introduce the closure technique, unifying earlier sufficient conditions.

Subtleties & Limits

No good characterization of Hamiltonicity is known, and unless P = NP, none can be efficiently checkable. Major open and hard directions:

Barnette's Conjecture (1969, open): Every 3-connected, cubic, bipartite, planar graph is Hamiltonian. Still unresolved.
Lovász's path conjecture / vertex-transitive graphs: It is conjectured every connected vertex-transitive graph (with $> 2$ vertices) has a Hamiltonian path; verified in many cases but open in general. The five known exceptional non-Hamiltonian vertex-transitive graphs (e.g., the Petersen graph) all lack a Hamiltonian cycle but have a Hamiltonian path.
Hamilton-connectedness and pancyclicity: Strengthenings (a Hamiltonian cycle of every length, or between every vertex pair) have their own delicate threshold conditions (Bondy's metaconjecture: nearly any condition forcing Hamiltonicity forces pancyclicity).
Sharp thresholds in random graphs: In $G (n, p)$ , Hamiltonicity appears abruptly precisely when the last vertex of degree $\leq 1$ disappears (Komlós–Szemerédi, Bollobás), a beautiful sharp-threshold phenomenon.