Short note: Eulerian graph

An Euler circuit in a graph is a closed walk that uses every edge exactly once; a graph that has one is Eulerian. An Euler path uses every edge exactly once but need not be closed (such a graph is semi-Eulerian). The idea comes from Euler's solution of the Königsberg bridge problem (1736): that graph has no Euler path because all four land areas have odd degree.

Theorems (undirected, connected graph):

• It has an Euler circuit if and only if every vertex has even degree.
• It has an Euler path (not a circuit) if and only if exactly two vertices have odd degree; the path starts at one and ends at the other.

Directed graphs: an Euler circuit exists iff the graph is connected and in-degree = out-degree for every vertex.

Example (bowtie):

   a         d
   |\       /|
   | \     / |
   |  \   /  |
   |   \ /   |
   |    c    |
   |   / \   |
   |  /   \  |
   | /     \ |
   b         e

Edges: ab, ac, bc, cd, ce, de. Degrees: c = 4, all others 2. Every degree is even, so an Euler circuit exists: c → a → b → c → d → e → c.

Methods: Fleury's algorithm (do not cross a bridge unless forced) or Hierholzer's algorithm. Applications: route planning for mail delivery, snow-plowing and garbage collection.