Turning an Open Euler Trail Into a Circuit

From Two Odd Degrees to an Euler Circuit

An undirected graph with an open Euler trail has two different endpoints. The parity of the degrees at those endpoints is the obstacle to applying the Euler circuit characterization: precisely those two degrees are odd. Adding one edge between the endpoints changes each of those degrees by one, making them even. If the augmented graph is connected, the Euler circuit characterization then supplies a circuit using every edge. Removing the added edge from that circuit recovers an open Euler trail in the original graph.

Throughout, an original graph is finite and simple. An Euler trail is a trail that uses every edge exactly once; a trail may repeat vertices, but not edges. It is open when its starting and ending vertices differ. A closed Euler trail is an Euler circuit. In the augmentation, we allow a multigraph: parallel edges are permitted, and parallel edge instances are treated as distinct. This matters when the two odd-degree vertices are already adjacent.

The circuit result used here is the earlier Euler circuit characterization: a connected graph with at least one edge has an Euler circuit exactly when every vertex has even degree. We apply the result to the augmented multigraph, counting parallel edge instances separately. The point of this tutorial is to prove why this augmentation is exactly the right operation, and why removing the added edge returns a trail that uses precisely the original edges.

Why the Augmentation Works

First note how a trail constrains degrees. Whenever a trail passes through a vertex as an internal vertex, the arrival edge and departure edge use two incidences there. For a closed Euler trail this pairing accounts for all incidences, so every degree is even. For an open Euler trail, the incidences at each endpoint have one unpaired edge, while all incidences at other vertices pair up. Thus the two endpoints have odd degree and every other vertex has even degree.

Here is the same parity argument stated with the edge-use condition included.

Proof. Consider the sequence of edges in the trail, which uses every edge exactly once. At an internal occurrence of any vertex, the trail enters along one edge and leaves along another, pairing two incidences. If a vertex appears internally more than once, each such passage contributes another pair. At the starting vertex \(x\), the first edge has no preceding arrival edge, leaving one unpaired incidence; all its other incidences are paired. Therefore \(\deg(x)\) is odd. The same reasoning at the final vertex \(y\) leaves one unpaired incidence, so \(\deg(y)\) is odd. Every other vertex has all incidences paired and hence even degree. The endpoints are distinct because the trail is open. \(\square\)

Now suppose \(G\) is connected and has exactly two odd-degree vertices, \(x\) and \(y\). Add a new edge instance \(e^*\) with endpoints \(x,y\). The degree of each of \(x\) and \(y\) increases by one, changing each from odd to even. Every other degree remains unchanged and is already even. The augmented graph is connected because the original graph was connected, and adding an edge cannot destroy any existing connection. It has at least one edge, so the Euler circuit characterization applies.

To recover a trail, take an Euler circuit of the augmented graph. Since the circuit uses every edge instance, it uses \(e^*\) exactly once. Regard the circuit cyclically and start its written sequence at \(e^*\). In one direction around the circuit it has the form \(x,e^*,y,\ldots,x\), or the same form with \(x\) and \(y\) interchanged. Delete \(e^*\) and begin the remaining sequence at its other endpoint. What remains is a trail from \(y\) to \(x\) (or \(x\) to \(y\)). It uses every edge instance other than \(e^*\) exactly once, and those are exactly the edges of \(G\). The endpoints differ, so this is an open Euler trail in \(G\).

These arguments prove both directions of the theorem. An open Euler trail forces exactly two odd-degree vertices by the lemma. Conversely, for a connected graph with exactly two odd-degree vertices, the added edge makes all degrees even; the Euler circuit characterization gives a circuit, and deleting the added edge gives the required open trail.

Worked Examples

Conditions and Common Pitfalls

The two odd degrees are not enough on their own: connectedness is also required. For example, let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,45\}\). Vertices \(4\) and \(5\) are the only odd-degree vertices, but the triangle on \(\{1,2,3\}\) and the edge \(45\) are in separate components. Adding an edge between \(4\) and \(5\) leaves those components disconnected. The augmented graph therefore cannot have one Euler circuit using all its edges, and the original graph has no Euler trail using every edge.

A related mistake is to treat the augmented graph as simple even when \(x\) and \(y\) are already adjacent. In the second example, writing \(E\cup\{34\}=E\) would leave \(\deg(3)=3\) and \(\deg(4)=1\); it would not change either degree. The correction is to add a new edge instance parallel to the existing \(34\). Counting that instance raises both degrees by one, making them \(4\) and \(2\), respectively.

Finally, removing the added edge means removing that particular edge instance from the circuit, not deleting every edge with the same endpoints. When a parallel original edge exists, the circuit must use both instances, and only the artificial one is discarded. This distinction is what guarantees that the recovered trail still uses every original edge, including an original edge joining the two endpoints.

Why the Method Is Useful

The transformation reduces the open-trail question to a circuit question already characterized by degree parity and connectedness. Rather than search for an ordering of all edges directly, one checks the graph's connectivity and degrees, adds a single edge between the odd vertices, and applies the Euler circuit result. Any Euler circuit of the augmented graph can then be cut at the added edge to give an open Euler trail.

The argument also explains the exact role of the endpoints: they are precisely the vertices whose degree parity must change. Adding an edge between any other pair would not make all degrees even. The added edge is therefore not an arbitrary shortcut; it encodes the start and finish of the desired trail as one extra step that closes the route.