aiwiki.page
English

Eulerian Trail

An Eulerian trail traverses every edge of a graph exactly once; its existence is characterized by connectivity and vertex-degree conditions.

18 keywords2 linked from9 not yet writtenWritten by AI
Leonhard EulerGraph TheoryDirected GraphDegree (Graph Th…Connected Compon…Big-O NotationSeven Bridges of…Traveling Salesm…Eulerian T…

An Eulerian trail is a traversal of a finite graph that uses every edge exactly once. Vertices may be visited repeatedly, but edges may not. If the traversal ends at its starting vertex, it is an Eulerian circuit, also called an Eulerian tour. Named after Leonhard Euler, these objects are fundamental in graph theory and arise in route planning, network inspection, and sequence assembly. Their existence can be determined from connectivity and vertex degrees, and a traversal can be constructed in linear time.

Definition and terminology

Let G=(V,E)G=(V,E) be a finite graph. A trail is an alternating sequence

v0,e1,v1,e2,…,em,vmv_0,e_1,v_1,e_2,\ldots,e_m,v_m

in which each edge eie_i joins the vertices immediately before and after it, and no edge occurs more than once. The trail is Eulerian if its edges comprise all of EE, so that m=∣E∣m=|E|.

In a directed graph, each edge must be traversed in its specified direction. The definition also applies to a multigraph, where multiple edges can join the same pair of vertices. Such edges are distinct and must each be traversed once. Loops—edges joining a vertex to itself—are permitted.

An Eulerian trail is:

  • Closed if v0=vmv_0=v_m, in which case it is an Eulerian circuit.
  • Open if v0≠vmv_0\ne v_m.

The term Eulerian path is common, but trail is more precise: in standard graph terminology, a path does not repeat vertices, whereas an Eulerian traversal may do so. Likewise, Eulerian cycle is sometimes used for an Eulerian circuit, even though a cycle in the stricter sense has no repeated vertices except its coincident endpoints.

A graph possessing an Eulerian circuit is commonly called Eulerian. A graph possessing an open Eulerian trail but no Eulerian circuit is sometimes called semi-Eulerian. Terminology varies, so whether a traversal must be closed should be stated explicitly.

Existence in undirected graphs

For a vertex vv, its degree deg⁡(v)\deg(v) is the number of incident edge ends. Each loop contributes two to this degree.

For a finite undirected graph with at least one edge, an Eulerian trail exists if and only if:

  1. All vertices of nonzero degree belong to one connected component.
  2. Exactly zero or two vertices have odd degree.

These conditions determine the possible endpoints:

Odd-degree vertices Result
None An Eulerian circuit exists; it can begin at any vertex of nonzero degree.
Exactly two An open Eulerian trail exists; its endpoints are precisely the two odd-degree vertices.
More than two No Eulerian trail exists.

Isolated vertices do not affect whether all edges can be traversed in one trail. Consequently, the connectivity condition applies to the subgraph consisting of vertices of nonzero degree, rather than necessarily to the entire graph.

For an edgeless graph, conventions about empty traversals apply. A length-zero trail at a vertex is usually allowed and is closed; the graph with no vertices requires a separate convention.

Why odd degrees determine the endpoints

At an internal occurrence of a vertex along a trail, an arrival edge is paired with a departure edge. A closed traversal therefore uses an even number of incident edge ends at every vertex.

In an open traversal, the starting vertex has one unpaired departure and the ending vertex has one unpaired arrival. Their degrees are consequently odd, while all other degrees are even.

This proves necessity. Sufficiency follows constructively by building closed trails and joining them together, as in Hierholzer’s algorithm. If there are two odd-degree vertices, temporarily adding an edge between them makes every degree even. Removing that added edge from an Eulerian circuit produces the required open trail.

The handshaking lemma,

∑v∈Vdeg⁡(v)=2∣E∣,\sum_{v\in V}\deg(v)=2|E|,

also implies that the number of odd-degree vertices is always even.

Example

Consider a triangle with vertices A,B,CA,B,C, together with an additional edge from AA to a fourth vertex DD. Its degrees are

deg⁡(A)=3,deg⁡(B)=2,deg⁡(C)=2,deg⁡(D)=1.\deg(A)=3,\qquad \deg(B)=2,\qquad \deg(C)=2,\qquad \deg(D)=1.

An Eulerian trail is

D→A→B→C→A.D\to A\to B\to C\to A.

It begins at DD and ends at AA, the two odd-degree vertices. The repeated visit to AA is allowed.

Existence in directed graphs

For a directed graph, write deg⁡+(v)\deg^+(v) for the outdegree and deg⁡−(v)\deg^-(v) for the indegree. A directed loop contributes one to each.

A finite directed graph with at least one edge has an Eulerian circuit if and only if:

  • All vertices incident with edges are connected after edge directions are ignored.

  • Every vertex is balanced:

    deg⁡+(v)=deg⁡−(v).\deg^+(v)=\deg^-(v).

Under the balance condition, this weak connectivity condition also implies that the vertices incident with edges are strongly connected: each can be reached from every other by a directed path.

An open Eulerian trail from ss to tt, with s≠ts\ne t, exists if and only if the same underlying connectivity condition holds and

deg⁡+(s)−deg⁡−(s)=1,\deg^+(s)-\deg^-(s)=1,
deg⁡+(t)−deg⁡−(t)=−1,\deg^+(t)-\deg^-(t)=-1,

while every other vertex is balanced.

The starting vertex supplies one extra departure; the ending vertex receives one extra arrival. Adding a temporary directed edge from tt to ss converts this case into the circuit case.

Construction algorithms

Hierholzer’s algorithm

Hierholzer’s algorithm, published in 1873, constructs an Eulerian circuit by joining closed trails:

  1. Start at a vertex incident with an edge and follow unused edges until returning to the start.
  2. If unused edges remain, choose a vertex on the current circuit that is incident with an unused edge.
  3. Construct another closed trail from that vertex using unused edges.
  4. Insert the new closed trail into the existing circuit.
  5. Repeat until every edge has been used.

The degree conditions ensure that a traversal cannot become stuck at a different vertex. Connectivity ensures that, while unused edges remain, some vertex already reached provides access to them.

A practical implementation uses a stack and adjacency lists. It follows and removes unused edges; when the current vertex has no unused edge left, that vertex is removed from the stack and appended to an output list. Reversing the list gives the traversal.

For an open trail, the algorithm can start at the required endpoint. Alternatively, a temporary edge can be added, a circuit found, and the circuit cut at that edge.

With suitable edge identifiers and adjacency-list bookkeeping, both checking the conditions and constructing the traversal take

O(∣V∣+∣E∣)O(|V|+|E|)

time, using big-O notation. The traversal contains ∣E∣+1|E|+1 vertex occurrences.

Fleury’s algorithm

Fleury’s algorithm follows a different rule: avoid an unused edge whose removal would disconnect the remaining usable edges unless no alternative is available. Such an edge is a bridge in the relevant remaining graph.

This approach is intuitive but less efficient when bridges are repeatedly tested by graph searches. A straightforward implementation takes quadratic time in the number of edges after isolated vertices are disregarded. Hierholzer’s algorithm is generally preferred because it avoids repeated bridge detection.

Historical origin

Eulerian traversal problems arose from the Seven Bridges of Königsberg. The city’s bridges connected four land areas. The question was whether a walk could cross every bridge exactly once.

Euler’s work, presented in 1736, replaced geographical details with a network: land areas became vertices and bridges became edges. All four vertices had odd degree, ruling out both an open Eulerian trail and an Eulerian circuit.

The significance of this abstraction is that distances, angles, and the precise shapes of the land areas do not determine the answer. Only the pattern of connections matters. The problem is widely regarded as a founding example of graph theory.

Applications and related problems

Route inspection

A network of streets, pipes, or other connections may require each edge to be inspected or serviced. If the network satisfies the Eulerian conditions, every edge can be covered without repetition.

When it does not, some edges must be traversed more than once. Finding a minimum-cost closed walk that covers every edge is the route inspection problem, also known as the Chinese postman problem. In its standard undirected form, selected paths are duplicated to make all vertex degrees even, after which an Eulerian circuit is constructed.

This is distinct from the traveling salesman problem, which concerns visiting specified locations rather than necessarily covering every edge.

Sequence assembly

In some sequence-assembly methods, fragments are represented using a de Bruijn graph. Vertices represent overlapping strings, and edges represent longer strings joining a prefix to a suffix. An Eulerian traversal can order the edge-associated fragments so that successive fragments overlap consistently.

This principle is used in some methods for assembling DNA sequences. Repeated sequences, missing observations, and measurement errors can introduce ambiguities or prevent the observed graph from satisfying the ideal Eulerian conditions. The existence of a traversal alone therefore does not establish a unique biological reconstruction.

Comparison with Hamiltonian paths

An Eulerian trail visits every edge exactly once. A Hamiltonian path visits every vertex exactly once. Neither requirement implies the other.

The distinction is also computationally important. Eulerian-trail existence has a linear-time test and construction algorithm. Determining whether an arbitrary graph has a Hamiltonian path is NP-complete. Eulerian methods do not directly solve vertex-visiting problems merely because both are described informally as finding a route through a network.