Necessary Conditions for Undirected Euler Trails

Two Necessary Tests for Using Every Edge

An undirected Euler trail uses every edge of a graph exactly once. For such a trail to exist, the edges cannot be split across disconnected parts of the graph: a single sequence of adjacent edges cannot travel between components. The degrees also impose a restriction. Whenever the trail reaches an intermediate vertex, it must leave by another edge; only its endpoints can have an unpaired arrival or departure. These observations give necessary conditions, not a proof that the conditions are sufficient.

All graphs in this tutorial are finite and simple. A trail is a walk that does not repeat an edge; it may repeat vertices. An Euler trail is a trail that uses every edge of the graph exactly once. If its first and last vertices are the same, it is an Euler circuit. If they are different, it is an open Euler trail. We consider graphs with at least one edge, so the trail under discussion has positive length.

The edge-support condition is deliberately weaker than requiring the whole graph to be connected. An isolated vertex has no edge to use, so its presence does not by itself prevent a trail from using every edge. By contrast, if two components each contain an edge, one trail cannot cover both.

The Necessary Connectivity and Parity Conditions

Proof. Write the Euler trail as \(v_0,e_1,v_1,\dots,e_m,v_m\), where each \(e_i\) joins \(v_{i-1}\) to \(v_i\), and every edge of \(G\) occurs exactly once. Every vertex in \(V^+\) appears in this sequence, because it is incident with an edge and every edge is used. For any two vertices appearing in the sequence, the part of the sequence between their appearances is a walk joining them. A walk contains a path between its endpoints (delete any section between repeated occurrences of a vertex). Thus every two vertices in \(V^+\) are joined by a path, and the edge-support is connected.

For the degree statements, count the incidences of edges at each vertex. Since the trail uses every edge exactly once, it accounts for every incidence at that vertex, and their number is its degree. At any internal position \(v_i\), with \(0<i<m\), the trail uses one edge to arrive and another to leave. Those are distinct edges because the trail does not repeat edges, so this visit contributes two incidences. Repeated internal visits also contribute pairs. If the trail is closed, \(v_0=v_m\); the first and last edges contribute two more incidences at that vertex. Every degree is therefore even. If the trail is open, \(v_0\ne v_m\); each endpoint has one unpaired incidence from its endpoint position, and all its other appearances contribute pairs. Each endpoint has odd degree, while every other vertex has only paired incidences and even degree. Isolated vertices have degree zero, which is even. These cases also show that there are either zero or two odd-degree vertices, with exactly two in the open case. \(\square\)

The connectivity and parity tests are separate: passing one does not make the other unnecessary. When ruling out a trail, either a disconnected edge-support or the wrong number of odd-degree vertices is enough. When using the conditions to assess a possible trail, remember that this tutorial establishes necessity only; it does not claim that passing the tests by itself proves a trail exists.

Worked Examples

How to Apply the Conditions

For a graph with at least one edge, an efficient first assessment is to calculate degrees and inspect the edge-support. These checks can disprove the existence of an Euler trail, but a failed check does not say which other property is responsible, so it is useful to record both.

The degree parity rule can also be understood locally. Along a trail, each intermediate arrival at a vertex is matched by a departure along another edge. A closed trail has no unpaired endpoint incidences. An open trail has one at each of its two endpoints. This explains why the number of odd-degree vertices is so tightly constrained, but it does not make vertex degrees a record of the order in which edges can be traversed.

Common Mistakes

Requiring the entire graph to be connected. In the third example, vertex \(5\) is isolated, so the whole graph is disconnected. Nevertheless, the displayed trail uses every edge. The relevant necessary condition is that the edge-support be connected, not that every vertex—including isolated vertices—belong to the same component.

Treating two odd vertices as a guarantee. In the first example, there are exactly two odd-degree vertices, but the edge-support has two components. The parity count is necessary for an open Euler trail; by itself it does not overcome a connectivity failure.

Confusing the open and closed cases. A closed Euler trail has no distinct endpoints, and every degree must be even. An open Euler trail has two distinct endpoints, which must be odd; its other vertices must be even. For instance, the third example has two odd-degree vertices, so its exhibited trail is open rather than closed.

These distinctions let you use degree parity and connectivity as reliable obstruction tests. A degree count should be made for every vertex, including isolated vertices (whose degree is zero), while connectivity should be checked among the vertices that actually have incident edges.