Eulerian Cycle — Definition, Formula & Examples

An Eulerian cycle is a closed walk through a graph that traverses every edge exactly once and returns to the starting vertex. It exists if and only if the graph is connected (ignoring isolated vertices) and every vertex has even degree.

Let $G = (V, E)$ be a connected graph with no isolated vertices. An Eulerian cycle (also called an Eulerian circuit) is a closed trail $v_0, e_1, v_1, e_2, \ldots, e_m, v_0$ that includes every edge in $E$ exactly once. By Euler's theorem, $G$ admits an Eulerian cycle if and only if every vertex $v \in V$ satisfies $\deg(v) \equiv 0 \pmod{2}$ .

How It Works

To determine whether a graph has an Eulerian cycle, check two conditions: the graph must be connected (considering only vertices with positive degree), and every vertex must have even degree. If either condition fails, no Eulerian cycle exists. To actually find the cycle, algorithms such as Hierholzer's algorithm work by building sub-tours and splicing them together. You start at any vertex, follow unused edges until you return to the start, then expand the tour by inserting detours from vertices that still have unused edges.

Worked Example

Problem: Determine whether the graph with vertices {A, B, C, D} and edges {AB, AC, BC, BD, CD} has an Eulerian cycle.

Step 1: Check connectivity: Every vertex is reachable from every other vertex, so the graph is connected.

Step 2: Compute vertex degrees: Count the edges incident to each vertex.

\deg(A) = 2,\quad \deg(B) = 3,\quad \deg(C) = 3,\quad \deg(D) = 2

Step 3: Check parity: Vertices B and C have odd degree. Since not every vertex has even degree, the necessary condition fails.

Answer: No Eulerian cycle exists. (The graph does have an Eulerian path from B to C, since exactly two vertices have odd degree.)

Why It Matters

Eulerian cycles appear in DNA fragment assembly, network routing, and circuit design where every connection must be used exactly once. The problem originated with Euler's analysis of the Königsberg bridge problem in 1736, widely regarded as the birth of graph theory.

Common Mistakes

Mistake: Confusing an Eulerian cycle (visits every edge once) with a Hamiltonian cycle (visits every vertex once).

Correction: Eulerian cycles concern edges; Hamiltonian cycles concern vertices. The existence conditions and computational complexity are entirely different.