Eulerian Path — Definition, Formula & Examples

An Eulerian path is a trail through a graph that traverses every edge exactly once. It may start and end at different vertices, unlike an Eulerian circuit which must return to its starting vertex.

Given a graph $G = (V, E)$ , an Eulerian path is a sequence of vertices $v_0, v_1, \dots, v_m$ such that each $(v_{i}, v_{i+1})$ is a distinct edge in $E$ , every edge in $E$ appears exactly once in the sequence, and $v_0$ may or may not equal $v_m$ . For an undirected connected graph, an Eulerian path exists if and only if the graph has exactly zero or exactly two vertices of odd degree.

How It Works

To determine whether a graph has an Eulerian path, first check that the graph is connected (ignoring isolated vertices). Then count the degree of every vertex. If exactly zero vertices have odd degree, an Eulerian circuit exists (a special case of an Eulerian path that starts and ends at the same vertex). If exactly two vertices have odd degree, an Eulerian path exists that starts at one odd-degree vertex and ends at the other. If more than two vertices have odd degree, no Eulerian path exists. To actually find the path, algorithms such as Hierholzer's algorithm efficiently construct one in

O(|E|)

time.

Worked Example

Problem: Determine whether an Eulerian path exists in the graph with vertices {A, B, C, D} and edges {AB, AC, BC, BD, CD}. If so, identify the starting and ending vertices.

Step 1: Compute the degree of each vertex by counting its incident edges.

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

Step 2: Count the vertices with odd degree. Vertices B and C each have degree 3, so there are exactly two odd-degree vertices.

Step 3: Since the graph is connected and has exactly two vertices of odd degree, an Eulerian path exists. It must start at B and end at C (or vice versa). One such path is:

B \to A \to C \to B \to D \to C

Answer: An Eulerian path exists. One valid path is B → A → C → B → D → C, which traverses all 5 edges exactly once.

Why It Matters

Eulerian paths appear in DNA sequence assembly, where overlapping fragments must be stitched into a single strand visiting every overlap once. They also arise in circuit design and the classic Königsberg bridge problem, which launched graph theory as a field. Understanding Eulerian paths is a core topic in discrete mathematics and algorithms courses.

Common Mistakes

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

Correction: An Eulerian path is about edges; a Hamiltonian path is about vertices. The existence conditions and computational complexity are entirely different — checking for Eulerian paths is efficient, while the Hamiltonian path problem is NP-complete.