Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

From the Bridges of Königsberg to Euler's theorem on Eulerian circuits, directed Eulerian graphs, Hamiltonian cycles, the theorems of Ore and Dirac, and the NP-completeness of the Hamiltonian cycle problem.

Folio Official

March 1, 2026

1. The Bridges of Königsberg

In 1736, Euler investigated whether it was possible to walk through the city of Kö

Modeling the problem as a multigraph, vertex $A$ has degree $5$ and each of $B, C, D$ has degree $3$ . Since every vertex has odd degree, the theorem below implies that no Eulerian circuit exists.

2. Eulerian Circuits and Trails

Definition 1 (Eulerian circuit and Eulerian trail).

An Eulerian circuit of a graph

G

is a closed trail that traverses every edge of

G

exactly once. An Eulerian trail is a trail (not necessarily closed) that traverses every edge exactly once. A graph that possesses an Eulerian circuit is called an Eulerian graph.

Theorem 2 (Euler's theorem).

A connected graph

G

has an Eulerian circuit if and only if every vertex of

G

has even degree.

Proof.

(\Rightarrow)

Each time the Eulerian circuit passes through a vertex

v

, it uses one edge to enter and one edge to leave, contributing

2

de g (v)

. Since every edge is used exactly once,

de g (v)

is even.

(\Leftarrow)

Assume every vertex has even degree. We proceed by induction on the number of edges

m

. If

m = 0

, the result is trivial. Suppose

m \geq 1

Since every vertex has degree at least

2

, the graph contains a cycle

C

(start at any vertex and follow unvisited edges; finiteness forces a return to a previously visited vertex). Consider

G^{'} = G - E (C)

. Because

C

removes an even number of edges at each vertex, every vertex of

G^{'}

still has even degree. By the induction hypothesis, each connected component of

G^{'}

has an Eulerian circuit.

We now splice these circuits together: traverse

C

, and whenever

C

passes through a vertex that belongs to a component of

G^{'}

, detour along that component's Eulerian circuit before continuing along

C

. Since

G

is connected, every component of

G^{'}

shares at least one vertex with

C

, so the splicing covers all edges. □

Theorem 3 (Existence of an Eulerian trail).

A connected graph

G

has an Eulerian trail if and only if the number of vertices of odd degree is exactly

0

2

. In the former case the trail is a circuit; in the latter, the trail runs between the two odd-degree vertices.

Proof.

When there are exactly two vertices of odd degree, say

u

and

v

, add the edge

{u, v}

to obtain

G + {u, v}

, in which every vertex has even degree. By Euler's theorem,

G + {u, v}

has an Eulerian circuit. Deleting the added edge from this circuit yields an Eulerian trail from

u

v

. □

3. Directed Eulerian Graphs

Theorem 4 (Directed Euler's theorem).

A connected directed graph

D

has an Eulerian circuit (a directed closed trail traversing every arc exactly once) if and only if

de g^{+} (v) = de g^{-} (v)

(out-degree equals in-degree) for every vertex

v

Proof.

The argument parallels the undirected case. Each passage through a vertex uses one incoming and one outgoing arc, making

de g^{+} (v) = de g^{-} (v)

necessary. Sufficiency is established by extracting a directed cycle and inductively merging the circuits of the remaining components. □

4. Hamiltonian Cycles

Definition 5 (Hamiltonian cycle and Hamiltonian path).

A cycle that visits every vertex of

G

exactly once is called a Hamiltonian cycle. A path that visits every vertex exactly once is a Hamiltonian path. A graph possessing a Hamiltonian cycle is called a Hamiltonian graph.

The graph below has a Hamiltonian cycle $a \to b \to c \to d \to e \to a$ (thick edges) but is not Eulerian (vertex $a$ has degree $3$ , which is odd):

Remark 6.

An Eulerian circuit traverses every edge; a Hamiltonian cycle visits every vertex. The former can be decided in polynomial time, while the latter is dramatically harder.

Theorem 7 (Dirac's theorem (1952)).

G

is a simple graph on

n \geq 3

vertices with

de g (v) \geq n /2

for every vertex

v

, then

G

is Hamiltonian.

Proof.

Suppose, for contradiction, that

G

is a non-Hamiltonian graph with minimum degree at least

n /2

and the maximum possible number of edges. Since adding any edge to

G

would create a Hamiltonian cycle,

G

contains a Hamiltonian path

v_{1}, v_{2}, \dots, v_{n}

We have

v_{1} v_{n} \in / E (G)

(otherwise

G

would be Hamiltonian). Define the sets

S = {i ∣ v_{1} v_{i + 1} \in E (G), 1 \leq i \leq n - 1}, T = {i ∣ v_{i} v_{n} \in E (G), 1 \leq i \leq n - 1} .

Since

∣ S ∣ = de g (v_{1}) \geq n /2

and

∣ T ∣ = de g (v_{n}) \geq n /2

, and both

S

and

T

are subsets of

{1, \dots, n - 1}

, we have

∣ S ∣ + ∣ T ∣ \geq n

. By the pigeonhole principle,

S \cap T \neq = \emptyset

Pick

k \in S \cap T

. Then

v_{1} v_{k + 1} \in E

and

v_{k} v_{n} \in E

, so

v_{1}, v_{2}, \dots, v_{k}, v_{n}, v_{n - 1}, \dots, v_{k + 1}, v_{1}

is a Hamiltonian cycle, contradicting our assumption. □

Theorem 8 (Ore's theorem (1960)).

G

is a simple graph on

n \geq 3

vertices such that

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

for every pair of non-adjacent vertices

u, v

, then

G

is Hamiltonian.

Remark 9.

Dirac's theorem is a corollary of Ore's theorem: if

δ (G) \geq n /2

, then for any non-adjacent pair

u, v

we have

de g (u) + de g (v) \geq 2 \cdot n /2 = n

5. NP-Completeness

Remark 10.

The Hamiltonian cycle problem — deciding whether a given graph contains a Hamiltonian cycle — is

NP

-complete. It is one of the

21

problems shown to be

NP

-complete by Karp (1972). Assuming

P \neq = NP

, no polynomial-time algorithm exists. By contrast, the existence of an Eulerian circuit can be decided in

O (n + m)

time simply by checking that every vertex has even degree. This stark difference in computational complexity highlights a fundamental distinction between traversing all edges and visiting all vertices.

Graph Theory Discrete Mathematics Textbook 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

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Folio Official

March 1, 2026

1. The Bridges of Königsberg

In 1736, Euler investigated whether it was possible to walk through the city of Kö

Modeling the problem as a multigraph, vertex $A$ has degree $5$ and each of $B, C, D$ has degree $3$ . Since every vertex has odd degree, the theorem below implies that no Eulerian circuit exists.

2. Eulerian Circuits and Trails

Definition 1 (Eulerian circuit and Eulerian trail).

An Eulerian circuit of a graph

G

is a closed trail that traverses every edge of

G

exactly once. An Eulerian trail is a trail (not necessarily closed) that traverses every edge exactly once. A graph that possesses an Eulerian circuit is called an Eulerian graph.

Theorem 2 (Euler's theorem).

A connected graph

G

has an Eulerian circuit if and only if every vertex of

G

has even degree.

Proof.

(\Rightarrow)

Each time the Eulerian circuit passes through a vertex

v

, it uses one edge to enter and one edge to leave, contributing

2

de g (v)

. Since every edge is used exactly once,

de g (v)

is even.

(\Leftarrow)

Assume every vertex has even degree. We proceed by induction on the number of edges

m

. If

m = 0

, the result is trivial. Suppose

m \geq 1

Since every vertex has degree at least

2

, the graph contains a cycle

C

(start at any vertex and follow unvisited edges; finiteness forces a return to a previously visited vertex). Consider

G^{'} = G - E (C)

. Because

C

removes an even number of edges at each vertex, every vertex of

G^{'}

still has even degree. By the induction hypothesis, each connected component of

G^{'}

has an Eulerian circuit.

We now splice these circuits together: traverse

C

, and whenever

C

passes through a vertex that belongs to a component of

G^{'}

, detour along that component's Eulerian circuit before continuing along

C

. Since

G

is connected, every component of

G^{'}

shares at least one vertex with

C

, so the splicing covers all edges. □

Theorem 3 (Existence of an Eulerian trail).

A connected graph

G

has an Eulerian trail if and only if the number of vertices of odd degree is exactly

0

2

. In the former case the trail is a circuit; in the latter, the trail runs between the two odd-degree vertices.

Proof.

When there are exactly two vertices of odd degree, say

u

and

v

, add the edge

{u, v}

to obtain

G + {u, v}

, in which every vertex has even degree. By Euler's theorem,

G + {u, v}

has an Eulerian circuit. Deleting the added edge from this circuit yields an Eulerian trail from

u

v

. □

3. Directed Eulerian Graphs

Theorem 4 (Directed Euler's theorem).

A connected directed graph

D

has an Eulerian circuit (a directed closed trail traversing every arc exactly once) if and only if

de g^{+} (v) = de g^{-} (v)

(out-degree equals in-degree) for every vertex

v

Proof.

The argument parallels the undirected case. Each passage through a vertex uses one incoming and one outgoing arc, making

de g^{+} (v) = de g^{-} (v)

necessary. Sufficiency is established by extracting a directed cycle and inductively merging the circuits of the remaining components. □

4. Hamiltonian Cycles

Definition 5 (Hamiltonian cycle and Hamiltonian path).

A cycle that visits every vertex of

G

exactly once is called a Hamiltonian cycle. A path that visits every vertex exactly once is a Hamiltonian path. A graph possessing a Hamiltonian cycle is called a Hamiltonian graph.

The graph below has a Hamiltonian cycle $a \to b \to c \to d \to e \to a$ (thick edges) but is not Eulerian (vertex $a$ has degree $3$ , which is odd):

Remark 6.

An Eulerian circuit traverses every edge; a Hamiltonian cycle visits every vertex. The former can be decided in polynomial time, while the latter is dramatically harder.

Theorem 7 (Dirac's theorem (1952)).

G

is a simple graph on

n \geq 3

vertices with

de g (v) \geq n /2

for every vertex

v

, then

G

is Hamiltonian.

Proof.

Suppose, for contradiction, that

G

is a non-Hamiltonian graph with minimum degree at least

n /2

and the maximum possible number of edges. Since adding any edge to

G

would create a Hamiltonian cycle,

G

contains a Hamiltonian path

v_{1}, v_{2}, \dots, v_{n}

We have

v_{1} v_{n} \in / E (G)

(otherwise

G

would be Hamiltonian). Define the sets

S = {i ∣ v_{1} v_{i + 1} \in E (G), 1 \leq i \leq n - 1}, T = {i ∣ v_{i} v_{n} \in E (G), 1 \leq i \leq n - 1} .

Since

∣ S ∣ = de g (v_{1}) \geq n /2

and

∣ T ∣ = de g (v_{n}) \geq n /2

, and both

S

and

T

are subsets of

{1, \dots, n - 1}

, we have

∣ S ∣ + ∣ T ∣ \geq n

. By the pigeonhole principle,

S \cap T \neq = \emptyset

Pick

k \in S \cap T

. Then

v_{1} v_{k + 1} \in E

and

v_{k} v_{n} \in E

, so

v_{1}, v_{2}, \dots, v_{k}, v_{n}, v_{n - 1}, \dots, v_{k + 1}, v_{1}

is a Hamiltonian cycle, contradicting our assumption. □

Theorem 8 (Ore's theorem (1960)).

G

is a simple graph on

n \geq 3

vertices such that

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

for every pair of non-adjacent vertices

u, v

, then

G

is Hamiltonian.

Remark 9.

Dirac's theorem is a corollary of Ore's theorem: if

δ (G) \geq n /2

, then for any non-adjacent pair

u, v

we have

de g (u) + de g (v) \geq 2 \cdot n /2 = n

5. NP-Completeness

Remark 10.

The Hamiltonian cycle problem — deciding whether a given graph contains a Hamiltonian cycle — is

NP

-complete. It is one of the

21

problems shown to be

NP

-complete by Karp (1972). Assuming

P \neq = NP

, no polynomial-time algorithm exists. By contrast, the existence of an Eulerian circuit can be decided in

O (n + m)

Graph Theory Discrete Mathematics Textbook 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

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

1. The Bridges of Königsberg

2. Eulerian Circuits and Trails

3. Directed Eulerian Graphs

4. Hamiltonian Cycles

5. NP-Completeness

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

1. The Bridges of Königsberg

2. Eulerian Circuits and Trails

3. Directed Eulerian Graphs

4. Hamiltonian Cycles

5. NP-Completeness

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums