The Euler--Hamilton divide: why "all edges" and "all vertices" are worlds apart

Determining whether a graph has an Eulerian circuit (traversing every edge exactly once) reduces to checking vertex degrees. Determining whether it has a Hamiltonian cycle (visiting every vertex exactly once) is NP-complete. This article explains why one word makes all the difference.

Folio Official

March 1, 2026

Graph theory harbors two problems that appear almost identical on the surface but differ astronomically in computational difficulty. An Eulerian circuit traverses every edge exactly once and returns to the start. A Hamiltonian cycle visits every vertex exactly once and returns to the start.

The first can be decided in polynomial time; the second is NP-complete – as far as anyone knows, no polynomial-time algorithm exists. "All edges" versus "all vertices": how can a single-word substitution produce such a gulf?

1. Eulerian circuits – just count the degrees

Definition 1 (Eulerian circuit).

A closed walk in a connected graph

G

that traverses every edge exactly once is called an Eulerian circuit.

Theorem 2 (Euler's theorem).

A connected graph

G

possesses an Eulerian circuit if and only if every vertex has even degree.

This criterion is strikingly simple. Checking whether every vertex has even degree takes $O (∣ V ∣ + ∣ E ∣)$ time.

Remark 3 (Why even degree is necessary and sufficient).

Think of what happens each time the circuit passes through a vertex

v

: it consumes one incoming edge and one outgoing edge. To use up all edges incident to

v

, the edges must pair off as "enter, exit, enter, exit, …." This is possible if and only if the degree is even.

If any vertex has odd degree, one edge is left over, and the circuit cannot close.

Example 4 (The bridges of Königsberg).

In the very first article of this series, we introduced the bridges of Kö– and Euler proved precisely this.

2. Hamiltonian cycles – even deciding existence is hard

Definition 5 (Hamiltonian cycle).

A cycle in a graph

G

that visits every vertex exactly once is called a Hamiltonian cycle.

Eulerian circuits enjoy the elegant criterion "every vertex has even degree." Is there an analogous characterization for Hamiltonian cycles?

Almost certainly not.

Theorem 6.

Deciding whether a graph contains a Hamiltonian cycle is NP-complete.

Some sufficient conditions are known:

Theorem 7 (Dirac's theorem).

G

is a simple graph on

n \geq 3

vertices and every vertex has degree at least

n /2

, then

G

contains a Hamiltonian cycle.

Theorem 8 (Ore's theorem).

G

is a simple graph on

n \geq 3

vertices and

de g (u) + de g (v) \geq n

for every pair of non-adjacent vertices

u, v

, then

G

contains a Hamiltonian cycle.

But these are merely sufficient conditions, not characterizations. Many graphs that fail these conditions still possess Hamiltonian cycles.

3. Why such a vast difference? – locality versus globality

Where does this dramatic gap come from?

Remark 9 (Edges are local; vertex visitation is global).

Notice that the Eulerian criterion – "every vertex has even degree" – is a local condition. It can be verified by examining each vertex independently.

A Hamiltonian cycle, by contrast, requires visiting every vertex exactly once. Whether a particular vertex should be visited at a particular point depends on which other vertices have already been visited – a constraint that is intrinsically global.

Let us make this more concrete.

Example 10 (Greedy construction fails).

Try to build a Hamiltonian cycle greedily in the following graph:

Starting at

A

, going to

B

, then

C

, then back to

A

leaves

D

unvisited. The path

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

succeeds, but the outcome hinges on the very first choice.

For Eulerian circuits, even if the traversal gets "stuck," recovery is always possible (Hierholzer's algorithm exploits this). The local guarantee of even degree means that at every vertex, there is always a way forward until all edges are exhausted. For Hamiltonian cycles, an early vertex choice can have irreversible consequences at the other end of the graph, and no local fix can compensate.

4. The complexity-theoretic perspective

This difference can be stated precisely in the language of complexity theory.

Remark 11.

The existence of an Eulerian circuit can be decided in

P

(polynomial time):

O (∣ V ∣ + ∣ E ∣)

suffices, and the circuit itself can be constructed just as efficiently.

The existence of a Hamiltonian cycle is

NP

-complete. Given a candidate vertex sequence, verifying that it is a Hamiltonian cycle takes

O (n)

time. But finding one (assuming

P \neq = NP

) requires super-polynomial time.

Remark 12 (A lesson from competitive programming).

In competitive programming, the contrast is felt acutely:

Eulerian path/circuit problems are standard fare: "check degrees, then run Hierholzer."
Hamiltonian cycle problems demand bitmask DP in $O (2^{n} \cdot n)$ (the traveling salesman approach).
An Eulerian path problem with $n = 1 0^{5}$ vertices is routine, while a Hamiltonian cycle problem is only feasible for $n \leq 20$ .

5. The traveling salesman problem

The optimization version of the Hamiltonian cycle problem is the celebrated Traveling Salesman Problem (TSP).

Definition 13 (Traveling salesman problem).

Given a complete graph

K_{n}

with weighted edges, find the minimum-cost cycle that visits every vertex exactly once and returns to the start.

TSP is NP-hard. Exact solutions can be computed by bitmask DP in $O (2^{n} \cdot n^{2})$ , but for practical purposes one typically resorts to approximation algorithms and heuristics.

6. Takeaway – one word changes everything

Eulerian circuit: "traverse every edge once" $\to$ local condition (even degrees) $\to$ $P$
Hamiltonian cycle: "visit every vertex once" $\to$ global constraint $\to$ $NP$ -complete

The chasm between "edges" and "vertices" carries a lesson that extends far beyond graph theory: problems characterized by local conditions tend to be efficiently solvable, while problems requiring global consistency tend to be explosively hard.

In the next article, we examine another beautiful duality in graph theory – the max-flow min-cut theorem.

Graph Theory Mathematics Between the Lines Eulerian Graphs Hamiltonian Graphs NP-Completeness

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The Euler--Hamilton divide: why "all edges" and "all vertices" are worlds apart

Folio Official

March 1, 2026

1. Eulerian circuits – just count the degrees

Definition 1 (Eulerian circuit).

A closed walk in a connected graph

G

that traverses every edge exactly once is called an Eulerian circuit.

Theorem 2 (Euler's theorem).

A connected graph

G

possesses an Eulerian circuit if and only if every vertex has even degree.

This criterion is strikingly simple. Checking whether every vertex has even degree takes $O (∣ V ∣ + ∣ E ∣)$ time.

Remark 3 (Why even degree is necessary and sufficient).

Think of what happens each time the circuit passes through a vertex

v

: it consumes one incoming edge and one outgoing edge. To use up all edges incident to

v

, the edges must pair off as "enter, exit, enter, exit, …." This is possible if and only if the degree is even.

If any vertex has odd degree, one edge is left over, and the circuit cannot close.

Example 4 (The bridges of Königsberg).

In the very first article of this series, we introduced the bridges of Kö– and Euler proved precisely this.

2. Hamiltonian cycles – even deciding existence is hard

Definition 5 (Hamiltonian cycle).

A cycle in a graph

G

that visits every vertex exactly once is called a Hamiltonian cycle.

Eulerian circuits enjoy the elegant criterion "every vertex has even degree." Is there an analogous characterization for Hamiltonian cycles?

Almost certainly not.

Theorem 6.

Deciding whether a graph contains a Hamiltonian cycle is NP-complete.

Some sufficient conditions are known:

Theorem 7 (Dirac's theorem).

G

is a simple graph on

n \geq 3

vertices and every vertex has degree at least

n /2

, then

G

contains a Hamiltonian cycle.

Theorem 8 (Ore's theorem).

G

is a simple graph on

n \geq 3

vertices and

de g (u) + de g (v) \geq n

for every pair of non-adjacent vertices

u, v

, then

G

contains a Hamiltonian cycle.

But these are merely sufficient conditions, not characterizations. Many graphs that fail these conditions still possess Hamiltonian cycles.

3. Why such a vast difference? – locality versus globality

Where does this dramatic gap come from?

Remark 9 (Edges are local; vertex visitation is global).

Notice that the Eulerian criterion – "every vertex has even degree" – is a local condition. It can be verified by examining each vertex independently.

Let us make this more concrete.

Example 10 (Greedy construction fails).

Try to build a Hamiltonian cycle greedily in the following graph:

Starting at

A

, going to

B

, then

C

, then back to

A

leaves

D

unvisited. The path

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

succeeds, but the outcome hinges on the very first choice.

4. The complexity-theoretic perspective

This difference can be stated precisely in the language of complexity theory.

Remark 11.

The existence of an Eulerian circuit can be decided in

P

(polynomial time):

O (∣ V ∣ + ∣ E ∣)

suffices, and the circuit itself can be constructed just as efficiently.

The existence of a Hamiltonian cycle is

NP

-complete. Given a candidate vertex sequence, verifying that it is a Hamiltonian cycle takes

O (n)

time. But finding one (assuming

P \neq = NP

) requires super-polynomial time.

Remark 12 (A lesson from competitive programming).

In competitive programming, the contrast is felt acutely:

Eulerian path/circuit problems are standard fare: "check degrees, then run Hierholzer."
Hamiltonian cycle problems demand bitmask DP in $O (2^{n} \cdot n)$ (the traveling salesman approach).
An Eulerian path problem with $n = 1 0^{5}$ vertices is routine, while a Hamiltonian cycle problem is only feasible for $n \leq 20$ .

5. The traveling salesman problem

The optimization version of the Hamiltonian cycle problem is the celebrated Traveling Salesman Problem (TSP).

Definition 13 (Traveling salesman problem).

Given a complete graph

K_{n}

with weighted edges, find the minimum-cost cycle that visits every vertex exactly once and returns to the start.

TSP is NP-hard. Exact solutions can be computed by bitmask DP in $O (2^{n} \cdot n^{2})$ , but for practical purposes one typically resorts to approximation algorithms and heuristics.

6. Takeaway – one word changes everything

Eulerian circuit: "traverse every edge once" $\to$ local condition (even degrees) $\to$ $P$
Hamiltonian cycle: "visit every vertex once" $\to$ global constraint $\to$ $NP$ -complete

In the next article, we examine another beautiful duality in graph theory – the max-flow min-cut theorem.

Graph Theory Mathematics Between the Lines Eulerian Graphs Hamiltonian Graphs NP-Completeness

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

The Euler--Hamilton divide: why "all edges" and "all vertices" are worlds apart

1. Eulerian circuits – just count the degrees

2. Hamiltonian cycles – even deciding existence is hard

3. Why such a vast difference? – locality versus globality

4. The complexity-theoretic perspective

5. The traveling salesman problem

6. Takeaway – one word changes everything

Share your expertise with the world

More from Folio Official

What the max-flow min-cut theorem is really saying — Duality in action

Why does the greedy algorithm work for trees? — What matroids reveal

Why are trees special? — The beauty of minimal connectivity

The magic of bipartite graphs — Why everything works

The Euler--Hamilton divide: why "all edges" and "all vertices" are worlds apart

1. Eulerian circuits – just count the degrees

2. Hamiltonian cycles – even deciding existence is hard

3. Why such a vast difference? – locality versus globality

4. The complexity-theoretic perspective

5. The traveling salesman problem

6. Takeaway – one word changes everything

Share your expertise with the world

More from Folio Official

What the max-flow min-cut theorem is really saying — Duality in action

Why does the greedy algorithm work for trees? — What matroids reveal

Why are trees special? — The beauty of minimal connectivity

The magic of bipartite graphs — Why everything works