Eulerian Circuits and Paths

Eulerian graph theory originated with Euler's 1736 solution to the Seven Bridges of Königsberg problem, marking the birth of graph theory. The question asks whether one can traverse all edges exactly once, returning to the starting point.

DefinitionEulerian Circuit and Path

An Eulerian circuit (or Eulerian cycle) is a closed walk that traverses every edge of a graph exactly once. An Eulerian path traverses every edge exactly once but need not return to the starting vertex.

A graph is Eulerian if it contains an Eulerian circuit, and semi-Eulerian if it contains an Eulerian path but no Eulerian circuit.

TheoremEuler's Theorem for Eulerian Circuits

A connected graph $G$ has an Eulerian circuit if and only if every vertex has even degree.

This elegant characterization provides a simple local condition (vertex degrees) for a global property (existence of an Eulerian circuit).

ProofProof Sketch

( $\Rightarrow$ ) If an Eulerian circuit exists, each time it visits a vertex $v$ , it uses two edges (one entering, one leaving). Since every edge is traversed exactly once, the degree of $v$ equals twice the number of visits, hence even.

( $\Leftarrow$ ) If all degrees are even, construct an Eulerian circuit by following edges arbitrarily. When stuck at vertex $v$ , we must be at the start (else we'd have odd degree at $v$ ). If not all edges are used, find an unused edge on the circuit and extend, maintaining even degrees in the remaining graph.

■

TheoremEuler's Theorem for Eulerian Paths

A connected graph $G$ has an Eulerian path if and only if it has exactly 0 or 2 vertices of odd degree.

If all degrees are even: Eulerian circuit exists (also an Eulerian path)
If exactly 2 odd-degree vertices: Eulerian path exists from one odd vertex to the other
Otherwise: No Eulerian path exists

ExampleSeven Bridges of Königsberg

The Königsberg graph has 4 vertices (land masses) with degrees $(3,3,3,5)$ —all odd. By Euler's theorem, no Eulerian path exists, proving it's impossible to walk across each bridge exactly once. This negative result was the first application of graph theory to solve a real-world problem.

DefinitionFleury's Algorithm

Fleury's Algorithm constructs an Eulerian circuit:

Start at any vertex $v$ (if Eulerian circuit exists)
At each step, choose any available edge, avoiding bridges of the remaining graph unless no alternative exists
Remove traversed edges and continue until all edges are used

Time complexity: $O(m^2)$ with careful implementation.

Remark

Hierholzer's algorithm improves efficiency to $O(m)$ by building partial cycles and merging them. Start from any vertex, follow edges until returning to start. If unused edges remain, find a vertex on the circuit with unused edges and build another cycle, then merge. This is optimal for practical Eulerian circuit construction.

Eulerian circuits appear in DNA sequencing (de Bruijn graphs), network routing (finding efficient routes covering all links), and genome assembly, demonstrating the enduring relevance of this classical problem.