An Euler circuit, also called an Euler tour, is an Eulerian trail whose final vertex equals its initial vertex. Its length is . It can revisit other vertices, unlike a Hamiltonian cycle, which visits each vertex once before returning to the start. For a finite undirected multigraph with at least one edge, an Euler circuit exists exactly when the edge support of a graph is a connected graph and every vertex degree is even.
For example, let be distinct parallel edges joining , let be a self-loop at , and add an isolated vertex . Then , and is an Euler tour. The self-loop supplies one traversal and two incidences; need not be visited. Replacing by a single edge changes both vertex degrees to odd numbers and removes the possibility of an Euler circuit. Thus collapsing parallel edges can change the answer.
Two triangles in a graph sharing one vertex give another instructive Euler circuit: . The shared vertex has vertex degree four, the others have vertex degree two, and is revisited between the two closed trails. This is precisely the splice used by Hierholzer's algorithm.
New to topics? Read the docs here!