Euler Graph — Definition, Formula & Examples

An Euler graph (also called an Eulerian graph) is a connected graph in which every vertex has even degree, meaning you can traverse every edge exactly once and return to where you started.

A finite, connected graph $G = (V, E)$ is Eulerian if and only if every vertex $v \in V$ has even degree, i.e., $\deg(v) \equiv 0 \pmod{2}$ for all $v$ . Equivalently, $G$ is Eulerian if it contains an Eulerian circuit — a closed trail that includes every edge of $G$ exactly once.

How It Works

To determine whether a graph is Eulerian, check two conditions: the graph must be connected (ignoring isolated vertices), and every vertex must have even degree. If both hold, an Eulerian circuit exists. If exactly two vertices have odd degree and the graph is connected, the graph has an Eulerian path (but not a circuit) and is called semi-Eulerian. Algorithms such as Hierholzer's algorithm can efficiently construct the actual circuit once you know it exists.

Worked Example

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

Step 1: 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 2: Check the even-degree condition: Vertices B and C each have odd degree (3). For an Euler graph, every vertex must have even degree.

Step 3: Conclude: Because exactly two vertices have odd degree, the graph is not Eulerian. However, it is semi-Eulerian: an Eulerian path exists from B to C (or C to B) that traverses every edge exactly once.

Answer: The graph is not an Euler graph (no Eulerian circuit), but it does have an Eulerian path since exactly two vertices have odd degree.

Why It Matters

Euler graphs originated with Euler's 1736 solution to the Königsberg Bridge Problem, widely considered the birth of graph theory. Today, identifying Eulerian circuits is essential in route optimization — for example, designing efficient routes for mail delivery, street sweeping, or network packet inspection where every link must be visited exactly once.

Common Mistakes

Mistake: Confusing Eulerian graphs with Hamiltonian graphs.

Correction: An Eulerian graph requires visiting every edge exactly once; a Hamiltonian graph requires visiting every vertex exactly once. The conditions and difficulty of checking them are entirely different.