Eulerian Graph — Definition, Formula & Examples
An Eulerian graph is a connected graph in which you can trace a path that travels along every edge exactly once and returns to the starting vertex. This closed path is called an Eulerian circuit (or Eulerian cycle).
A connected graph is Eulerian if and only if every vertex of has even degree. Equivalently, is Eulerian if it admits an Eulerian circuit — a closed trail that contains every edge of exactly once.
How It Works
To determine whether a graph is Eulerian, compute the degree of every vertex. If the graph is connected and every vertex has even degree, an Eulerian circuit exists. If exactly two vertices have odd degree (and the rest are even), the graph has an Eulerian trail (open, not a circuit) but is not Eulerian. If more than two vertices have odd degree, no Eulerian trail or circuit exists. Algorithms such as Hierholzer's algorithm can efficiently construct the 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 Eulerian.
Step 1: Find vertex degrees: Count the edges incident to each vertex.
Step 2: Check the degree condition: For an Eulerian circuit, every vertex must have even degree. Vertices B and C each have odd degree (3).
Step 3: Conclude: Since exactly two vertices have odd degree, the graph has an Eulerian trail (starting at B and ending at C, or vice versa) but does not have an Eulerian circuit. Therefore the graph is not Eulerian.
Answer: The graph is not Eulerian because vertices B and C have odd degree. It does, however, have an Eulerian trail.
Why It Matters
The concept originated from Euler's 1736 solution to the Königsberg Bridge Problem, widely regarded as the birth of graph theory. Eulerian circuits appear in practical settings such as designing efficient mail delivery routes, DNA fragment assembly in bioinformatics, and circuit board inspection where a machine must traverse every connection.
Common Mistakes
Mistake: Confusing Eulerian (visits every edge once) with Hamiltonian (visits every vertex once).
Correction: An Eulerian circuit covers all edges; a Hamiltonian cycle covers all vertices. The conditions for their existence are entirely different — Eulerian graphs are characterized by vertex degrees, while determining if a graph is Hamiltonian is NP-complete.