An Eulerian path is a walk through a graph that uses every edge exactly once. If such a walk begins and ends at the same vertex it is called an Eulerian circuit or Eulerian cycle. The concept is a central idea in graph theory and provides simple, checkable criteria that determine whether a given graph admits such a traversal.

Basic characterization

For undirected graphs the classical criterion is elementary: a connected graph has an Eulerian circuit exactly when every vertex has even degree. It has an Eulerian path (but not a circuit) exactly when it is connected and exactly two vertices have odd degree; such a path must start at one odd vertex and end at the other. For directed graphs the conditions involve in-degrees and out-degrees: a directed graph admits an Eulerian circuit when each vertex has equal in-degree and out-degree and the edges lie in a single strongly connected component (ignoring isolated vertices). A directed Eulerian path exists when, apart from equal in- and out-degrees at most vertices, one vertex has out-degree one greater than its in-degree (a start) and one has in-degree one greater than its out-degree (an end), together with an appropriate connectivity condition.

Historical context

The idea originated with Leonhard Euler's 1736 analysis of the Seven Bridges of Königsberg. Euler proved that no route could cross each of the city's bridges exactly once, reducing the layout to an abstract network of vertices and edges and laying foundations for graph theory and network reasoning.

Algorithms

Constructive methods can build Eulerian walks when they exist. Hierholzer's algorithm finds an Eulerian circuit in linear time by repeatedly following unused edges and splicing cycles. Fleury's algorithm is simpler conceptually but less efficient in practice because it checks bridge edges repeatedly. These procedures are widely taught as introductory graph algorithms.

Applications and examples

Eulerian paths appear in many practical problems: route inspection and urban planning (the Chinese postman problem seeks the shortest closed route that traverses all edges, possibly repeating some), DNA assembly approaches that model reads with de Bruijn graphs, utility network inspections, and recreational puzzles. Simple examples include any cycle graph (all vertices even degree) which is Eulerian, or a single path graph which has exactly two odd-degree endpoints and therefore an Eulerian trail but not a circuit.

Distinctions and notable facts

  • Eulerian vs Hamiltonian: Eulerian examines edge traversal, Hamiltonian requires visiting vertices once — different existence criteria and algorithms.
  • Checking for an Eulerian path is efficient: degree counts and connectivity tests suffice.
  • Euler's reasoning transformed practical route questions into abstract combinatorial criteria, influencing modern network theory.