# Eulerian path Every vertex of this graph has an even degree, therefore this is an Eulerian graph. Following the edges in alphabetical order gives an Eulerian circuit/cycle.

In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. Mathematically the problem can be stated like this:

Given the graph on the right, is it possible to construct a path (or a cycle, i.e. a path starting and ending on the same vertex) which visits each edge exactly once?

Graphs which allow the construction of so called Eulerian circuits are called Eulerian graphs. Euler observed that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and that for an Eulerian path either all, or all but two (i.e., the two endpoint) vertices have an even degree; this means the Königsberg graph is not Eulerian. Sometimes a graph that has an Eulerian path, but not an Eulerian circuit (in other words, it is an open path, and does not start and end at the same vertex) is called semi-Eulerian.

Carl Hierholzer published the first complete characterization of Eulerian graphs in 1873, by proving that in fact the Eulerian graphs are exactly the graphs which are connected and where every vertex has an even degree.

## Definition

An Eulerian path, Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. If such a path exists, the graph is called traversable or semi-eulerian.

An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses each edge exactly once. If such a cycle exists, the graph is called Eulerian or unicursal. The cycle starts and ends at the same vertex.

For directed graphs path has to be replaced with directed path and cycle with directed cycle.

The definition and properties of Eulerian paths, cycles and graphs are valid for multigraphs as well.