Eulerian and Hamiltonian Graphs

⚡ Key Takeaways

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.

💡 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.

DefinitionWalks, 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 \cdots 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.

DefinitionDegree and Handshake Identity

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

1

\quad \sum_{v \in V} \deg(v) = 2|E|

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

TheoremEuler'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.

2

\quad G \text{ Eulerian} \iff G \text{ connected (on edges)} \;\wedge\; \forall v\, \deg(v) \equiv 0 \pmod 2

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

TheoremDirected Euler Criterion

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

3

\quad D \text{ Eulerian} \iff \text{strongly connected (on edges)} \;\wedge\; \forall v\; d^{+}(v) = d^{-}(v)

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

TheoremDirac's Theorem, 1952

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

4

\quad \delta(G) \geq \frac{n}{2} \implies G \text{ Hamiltonian}

Derivation hint: 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.

TheoremOre's Theorem, 1960

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

5

\quad \deg(u) + \deg(v) \geq n \implies G \text{ Hamiltonian}

Derivation hint: same longest-path rotation argument as Dirac, but the degree budget is shared between the two path endpoints, generalizing $\delta \geq n/2$ .

TheoremBondy–Chvátal Closure, 1976

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

6

\quad G \text{ Hamiltonian} \iff \mathrm{cl}(G) \text{ Hamiltonian}

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

ProofEuler's Theorem — Necessity

Claim: If $G$ is Eulerian, every degree is even. 1. Let $W = v_0 e_1 v_1 \cdots e_m v_0$ be an Eulerian circuit traversing all $m = |E|$ edges exactly once. 2. 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. 3. 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$ . 4. Since every edge incident to $v$ appears exactly once in $W$ and they group into entering/leaving pairs, $\deg(v)$ is even. $\blacksquare$

∎

ProofEuler's Theorem — Sufficiency via Hierholzer

Claim: Connected + all-even-degree ⟹ Eulerian circuit, constructively. 1. 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$ . 2. If $C_1$ uses all edges, done. 3. 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$ . 4. 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. 5. 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|)$ . $\blacksquare$

∎

ProofOre's Theorem

1. Suppose, for contradiction, that $G$ satisfies the Ore condition $\deg(u)+\deg(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. 2. Then $G$ has a Hamiltonian path $x_1 x_2 \cdots x_n$ (adding the missing edge $x_1 x_n$ would complete a cycle, so the path spans all vertices). 3. 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| = \deg(x_1)$ and $|T| = \deg(x_n)$ . 4. Since $x_1, x_n$ are non-adjacent, $\deg(x_1)+\deg(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$ . 5. This yields the cycle $x_1 x_2 \cdots x_i x_n x_{n-1} \cdots x_{i+1} x_1$ through all $n$ vertices — a Hamiltonian cycle. Contradiction. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

ExampleEulerian trail in a small graph

Given: Graph on vertices $\{A,B,C,D,E\}$ with edges $AB, BC, CD, DA$ (a 4-cycle) plus $AC$ and $CE, EB$ .

Step 1 — Compute degrees:

$\deg(A) = |\{AB, DA, AC\}| = 3$
$\deg(B) = |\{AB, BC, EB\}| = 3$
$\deg(C) = |\{BC, CD, AC, CE\}| = 4$
$\deg(D) = |\{CD, DA\}| = 2$
$\deg(E) = |\{CE, EB\}| = 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: $AC, CD, DA, AB, BC, CE, EB$ — all 7 edges, each once.

\boxed{\text{Eulerian trail: } A\,C\,D\,A\,B\,C\,E\,B \text{ (open, } A \to B)}

ExampleApplying Dirac & Ore

Given: Simple graph $G$ on $n = 6$ vertices where every vertex has degree exactly $3$ .

Step 1 — Dirac test: Need $\delta(G) \geq n/2 = 3$ . Here $\delta = 3 \geq 3$ . ✓ Dirac satisfied ⟹ Hamiltonian. Concretely, the prism graph $K_3 \times K_2$ (two triangles $1\,2\,3$ and $4\,5\,6$ 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 $\deg(u) = \deg(v) = 2$ . Then $\deg(u)+\deg(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).

\boxed{\text{Prism } K_3\times K_2 \text{ is Hamiltonian; cycle } 1\,2\,3\,6\,5\,4\,1}

⚠️ Common mistake

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 \ll 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."

Counterexample

Eulerian but NOT Hamiltonian: Take two triangles sharing a single common vertex $v$ (a "bowtie"): vertices $\{v, a, b, c, d\}$ , edges $va, ab, bv, vc, cd, dv$ . Every vertex has even degree ( $\deg 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 ( $1\,2\,3\,4\,1$ ) but every vertex has degree $3$ (odd), so it has no Eulerian circuit. Hamiltonian ✓, Eulerian ✗.

connection

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.
<a class="wiki-link" href="/wiki/cs-theory-np-completeness">NP-Completeness</a> — 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).

🔬 Where this appears

⏳ History

- 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

\delta \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.

open-problem

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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also