Eulerian and Hamiltonian Paths — Mathematics Knowledge System

Overview

An Eulerian path traverses every EDGE of a graph exactly once; a Hamiltonian path visits every VERTEX exactly once. Despite the similar-sounding names, they behave completely differently: Euler's 1736 solution to the Seven Bridges of Königsberg gave a clean criterion — a connected graph has an Eulerian circuit if and only if every vertex has even degree, and an Eulerian path (not necessarily closed) if and only if exactly zero or two vertices have odd degree. No comparably simple criterion is known for Hamiltonian paths; determining whether one exists is NP-complete in general, making it one of the hardest classical problems in graph theory.

Intuition

An Eulerian path is a mail carrier who must walk down every street exactly once (edges matter); a Hamiltonian path is a traveling salesperson who must visit every house exactly once, regardless of which streets are used (vertices matter). The mail-carrier problem is easy to check — just count odd-degree intersections — but the salesperson problem has no known shortcut, which is why Hamiltonian-path and the related traveling-salesperson problems are computationally hard.

Formal Definition

Definition

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

\text{Eulerian circuit exists} \iff \deg(v) \text{ is even for every } v \in V

Euler's criterion (circuit)

\text{Eulerian path exists} \iff \text{exactly 0 or 2 vertices have odd degree}

Euler's criterion (path)

\text{Hamiltonian path: a path visiting every } v \in V \text{ exactly once}

Hamiltonian path (no simple criterion known)

Worked Examples

Count vertices with odd degree: all four vertices (3, 3, 3, 5) are odd.
$\text{odd-degree vertices} = 4$
Euler's criterion requires exactly 0 or 2 odd-degree vertices for a path to exist; here there are 4.
$4 \ne 0 \text{ and } 4 \ne 2$

Answer: No — with 4 odd-degree vertices, no Eulerian path exists, confirming Euler's original 1736 conclusion.

Practice Problems

Difficulty 3/10

A graph's degree sequence is 4, 4, 2, 2. Does it have an Eulerian circuit?

Difficulty 5/10

A neighborhood's street-intersection graph has exactly 2 intersections with an odd number of streets meeting there, and all others even. Can a mail carrier walk every street exactly once? Must they return to the start?

Difficulty 4/10

Why is testing for a Hamiltonian path fundamentally harder than testing for an Eulerian path, computationally?

Quiz

Summary

An Eulerian path/circuit uses every edge exactly once; existence is decided instantly by vertex degree parity (Euler, 1736).
A Hamiltonian path visits every vertex exactly once; no simple criterion is known and testing for one is NP-complete.
The contrast between the two is a classic example of how superficially similar graph problems can differ hugely in computational difficulty.

References

WebsiteWikipedia — Eulerian path