Eulerian & Hamiltonian Graphs

Euler paths by degree parity; Hamiltonian tours visit every vertex.

The idea

Theorem (Euler's criterion).

Let $G$ be a connected graph. Then $G$ has an Euler circuit if and only if every vertex of $G$ has even degree, and $G$ has an Euler path if and only if $0$ or $2$ of its vertices have odd degree.

A walk moves from vertex to vertex along edges of the graph. An Euler path is a walk that uses every edge exactly once; vertices may repeat, edges may not. An Euler circuit is an Euler path that ends at the vertex it started from. The degree of a vertex is the number of edges meeting it.

The criterion replaces a search with a count. Trying routes and failing to find one proves nothing, but counting the odd-degree vertices settles the question in both directions: it guarantees a route when one exists and proves impossibility when none does.

A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle is one that returns to its start. Despite the similarity of the definitions, no comparably simple test for a Hamiltonian path or cycle is known.

Ways to work on it

• Walkthrough. The odd-degree criterion and Königsberg.
• Proof. See why an Euler circuit forces every degree to be even.
• Practice. Read a graph and classify it: Euler circuit, Euler path, or neither.
• Hardest. Classify a small complete graph: Eulerian, Hamiltonian, both, or neither.

Not sure where to start? Take the ten-question placement test.