= Euler circuit
{c}
= Euler tour
{c}
{synonym}
An <Euler circuit>, also called an <Euler tour>, is an <Eulerian trail> whose final <vertex> equals its initial <vertex>. Its length is $|E|$. 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 $p,q$ be distinct parallel <edges> joining $A,B$, let $\ell$ be a <self-loop> at $A$, and add an <isolated vertex> $Z$. Then $(\deg(A),\deg(B),\deg(Z))=(4,2,0)$, and $A,\ell,A,p,B,q,A$ is an <Euler tour>. The <self-loop> supplies one traversal and two incidences; $Z$ need not be visited. Replacing $p,q$ 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> $A$ give another instructive <Euler circuit>: $A,B,C,A,D,E,A$. The shared <vertex> has <vertex degree> four, the others have <vertex degree> two, and $A$ is revisited between the two closed <trails>. This is precisely the splice used by <Hierholzer's algorithm>.
Back to article page
