Graph Concepts

Eulerian circuit and Eulerian trail

An Eulerian trail (pronounciation: "oy-LEHR-ee-un") is a trail that visits every edge of the graph once and only once. It can end on a vertex different from the one on which it began.

Eulerian trail An Eulerian trail
AFBCDECFDAB

An Eulerian circuit is an Eulerian trail that is a circuit. That is, it begins and ends on the same vertex.

Eulerian circuit An Eulerian circuit
AFBCDECFDA

A graph is called Eulerian when it contains an Eulerian circuit.

Eulerian circuits are named for the eighteenth-century Swiss mathematician Leonhard Euler who proposed the question from which graph theory originates. Usally a multigraph is used to explore this famous Bridges of Königsberg Problem. Euler proved a theorem that says a graph is Eulerian if and only if each of its vertices has even degree. This theorem applies to all kinds of pseudographs.