Eulerian trail
= Eulerian trail
{c}
= Eulerian path
{c}
{synonym}
An <Eulerian trail>, also called an <Eulerian path>, is a <trail in a graph> traversing every <edge> exactly once. The name <Eulerian path> does not require a <graph path>: <vertices> may repeat. A <Hamiltonian path> instead visits every <vertex> exactly once, and may omit <edges>. An <Eulerian trail> may omit <isolated vertices>, so these are different coverage requirements.
For a finite undirected <multigraph> with at least one <edge>, allowing <self-loops>, an <Eulerian trail> exists exactly when the <edge support of a graph> is a <connected graph> and there are zero or two <vertices> of odd <vertex degree>. In the two-odd-<vertex> case they must be the two distinct endpoints; in the zero-odd-<vertex> case every <Eulerian trail> is an <Euler circuit>. Count a <self-loop> twice in the <vertex degree> but once in the <trail>, and count each parallel <edge> separately.<Math 530: Graph Theory (Combinatorial Mathematics I), Spring 2023/Math 530 Spring 2023, Lecture 6: Multigraphs and digraphs>[pp. 1–3, Theorem 1.1.2 and the note about isolated vertices]{ref}
The <parity> obstruction is local: each intermediate visit pairs an arriving <edge> with a departing <edge>. Only the distinct endpoints can have an unpaired incidence. The <handshaking lemma>, $\sum_{v\in V}\deg(v)=2|E|$, also shows that the number of <vertices> with odd <vertex degree> is even. Sufficiency in the two-endpoint case reduces to the <Euler circuit criterion>: add one extra <edge> between the odd <vertices>, construct an <Euler circuit>, rotate its record to start with the extra <edge>, then delete that <edge>. The remaining <trail> has the required endpoints.
For the <Seven Bridges of Königsberg> <multigraph>, the <vertex degrees> at $A,B,C,D$ are $(5,3,3,3)$, so no <Eulerian trail> exists. Remove the unique <edge> $AD$: the <vertex degrees> become $(4,3,3,2)$, and a six-<edge> <Eulerian trail> runs from $B$ to $C$. Label the parallel <edges> $p_1,p_2$ between $A,B$ and $q_1,q_2$ between $A,C$; label $BD$ by $r$ and $CD$ by $s$. A complete record is $B,p_1,A,q_1,C,s,D,r,B,p_2,A,q_2,C$. It revisits $A,B,C$ while using every remaining <edge> once.
\Image[/eulerian-degree-parity-multigraphs.png]
{title=Four odd <vertex degrees> forbid an <Eulerian trail>; two allow distinct endpoints; zero allow an <Euler circuit>}