Open Euler Trails and Their Conditions
A directed Euler trail is a route that uses every arc exactly once while following each arc in its direction. For an open trail, the starting vertex and ending vertex are different. The main issue is to determine when the local degree requirements at those two vertices, together with a connectivity condition, are enough to guarantee such a trail.
Throughout, a digraph is finite and simple: it has no loops and at most one arc in each direction between any two distinct vertices. Both \(u\to v\) and \(v\to u\) may be present. A directed trail is a sequence of vertices and arcs that follows arc directions and does not repeat an arc; vertices may repeat. It is an Euler trail if it uses every arc of the digraph exactly once. It is open from \(s\) to \(t\) if its first vertex is \(s\), its last vertex is \(t\), and \(s\ne t\).
Weak connectivity does not mean that every vertex can be reached from every other vertex by following directed arcs. The relevant condition is that the arcs and their endpoints form one connected piece when directions are ignored.
Why the Conditions Are Necessary
Suppose an open Euler trail from \(s\) to \(t\) uses every arc. At \(s\), the trail leaves once more than it enters: it starts there and does not end there. At \(t\), it enters once more than it leaves. Whenever the trail visits any other vertex, each arrival is paired with a departure. Thus the stated degree differences hold.
Also, every non-isolated vertex is visited by the trail, because it is the endpoint of at least one arc, and every arc is used. The sequence of vertices in the trail gives a connected route through all those vertices when directions are ignored. Hence the support is weakly connected.
Worked Example: Checking a Valid Open Trail
Let \(G\) have vertex set \(V=\{s,a,b,t\}\) and arc set \(E=\{s\to a,a\to t,a\to b,b\to a\}\). Test the conditions and find an open Euler trail from \(s\) to \(t\).
The degrees are \(d^+(s)=1,d^-(s)=0\), so \(d^+(s)-d^-(s)=1-0=1\). At \(t\), \(d^+(t)=0,d^-(t)=1\), so \(d^-(t)-d^+(t)=1-0=1\). At \(a\), there are two outgoing arcs, \(a\to t\) and \(a\to b\), and two incoming arcs, \(s\to a\) and \(b\to a\); thus \(d^+(a)=2=d^-(a)\). At \(b\), \(d^+(b)=1=d^-(b)\). All four vertices are joined in the underlying undirected graph.
One route is \(s\to a\to b\to a\to t\). It uses, in order, \(s\to a\), \(a\to b\), \(b\to a\), and \(a\to t\), so every arc appears exactly once. As a check, its first vertex is \(s\), its last is \(t\), and these are distinct.
The Balanced-Circuit Lemma
For sufficiency, we first need a result about balanced digraphs. The auxiliary graph in its proof may have parallel arcs, so the lemma is stated for directed multigraphs. In a directed multigraph, arcs are distinguishable even when they have the same tail and head; loops are also allowed. Indegree and outdegree count arcs with their multiplicities.
Proof. Choose a non-isolated vertex \(r\). Starting at \(r\), follow unused outgoing arcs for as long as possible, never using an arc twice. This process stops because the multigraph has finitely many arcs. We first show that it stops at \(r\). If it stopped at a different vertex \(x\), the trail so far would have used one more arc entering \(x\) than leaving \(x\). Since the total indegree and outdegree of \(x\) are equal, the unused arcs would then include one more arc leaving \(x\) than entering \(x\). In particular, an unused outgoing arc would remain, contradicting that the process stopped. Thus the trail is closed.
Removing the arcs of a closed trail leaves equal unused indegree and outdegree at every vertex: at each vertex on the trail, its arrivals and departures occur in equal numbers, and vertices outside the trail lose no arcs. If unused arcs remain, there is a vertex on the closed trail with an unused outgoing arc. To justify this, let \(S\) be the set of vertices on the trail. If an unused arc has its tail in \(S\), the claim holds. Otherwise, take an endpoint of any unused arc and use weak connectivity to follow an undirected route from \(S\) to that endpoint. The first arc crossing from \(S\) to its complement cannot have been used, since every used arc has both endpoints in \(S\). If it points out of \(S\), it is an unused outgoing arc at a vertex in \(S\). If it points into \(S\), that vertex has an unused incoming arc; equality of its unused indegree and outdegree implies it also has an unused outgoing arc.
Start at a vertex in \(S\) with an unused outgoing arc and follow unused arcs until the process stops. The same degree argument, applied to the unused arcs, shows that this second trail closes at its starting vertex. Insert this closed trail into the first one at their shared vertex. The result is still a closed trail, with no repeated arcs, and it uses more arcs than before. Repeating this operation must terminate because each repetition adds at least one arc and there are only finitely many arcs. If any arc were still unused, the same argument would supply another closed trail to insert. Therefore the final closed trail uses every arc. \(\square\)
Proof of the Characterization
Proof. Necessity was established above. For sufficiency, suppose the support is weakly connected and the degree conditions hold. Add one new arc \(t\to s\), treating it as a distinguishable arc even if the original digraph already has an arc with those endpoints. The result is a directed multigraph. At \(s\), the added incoming arc removes the original excess of one outgoing arc. At \(t\), the added outgoing arc removes the original excess of one incoming arc. Every other vertex was already balanced. Thus every vertex has equal indegree and outdegree in the augmented multigraph.
The new arc has endpoints in the original support because the degree conditions imply that \(s\) and \(t\) are non-isolated. Adding an arc between two vertices in that support preserves weak connectivity there. The balanced-circuit lemma therefore gives a closed Euler trail in the augmented multigraph. Read that circuit cyclically starting just after the added arc \(t\to s\). It starts at \(s\), follows all the original arcs, and returns to \(t\) immediately before the added arc. Deleting the added arc leaves an open Euler trail from \(s\) to \(t\) in the original digraph. The new arc was distinguishable, so this deletion removes only the added arc, even if another arc \(t\to s\) was already present. \(\square\)
Worked Example: An Existing Arc with the Same Endpoints
Let \(G\) have \(V=\{s,a,t\}\) and \(E=\{s\to a,a\to t,t\to s,s\to t\}\). The original digraph is simple, but it already has an arc \(t\to s\), the same ordered pair used by the augmentation proof.
At \(s\), \(d^+(s)=2\) and \(d^-(s)=1\), so the difference is \(2-1=1\). At \(t\), \(d^-(t)=2\) and \(d^+(t)=1\), so the reverse difference is \(2-1=1\). At \(a\), \(d^+(a)=1=d^-(a)\). The support is weakly connected. The open Euler trail is \(s\to a\to t\to s\to t\), which uses the four listed arcs exactly once.
For the proof, add a new, distinguishable arc \(t\to s\). There are now two distinct arcs from \(t\) to \(s\). In the augmented multigraph, \(s\) has outdegree \(2\) and indegree \(2\); \(t\) has outdegree \(2\) and indegree \(2\); and \(a\) has outdegree \(1\) and indegree \(1\). The closed trail \(s\to a\to t\to s\to t\to s\) uses all five arcs, with its final \(t\to s\) being the added arc. Removing that added arc leaves the stated open trail. This example shows why the auxiliary lemma must allow distinguishable parallel arcs.
Testing the Connectivity Condition
Worked Example: Correct Imbalances but Disconnected Support
Let \(G\) have \(V=\{s,t,x,y\}\) and \(E=\{s\to t,x\to y,y\to x\}\). At \(s\), the outdegree difference is \(1-0=1\); at \(t\), the reverse difference is \(1-0=1\). At \(x\), both degrees are \(1\), and at \(y\), both degrees are \(1\). Thus all the degree conditions hold.
However, the support has two components when directions are ignored: one contains \(s,t\), and the other contains \(x,y\). The connectivity condition fails. There cannot be an Euler trail using every arc, because no arc connects the two components, so a trail that uses the arc \(s\to t\) cannot also use either arc between \(x\) and \(y\).
Check: the route \(s\to t\) uses the only arc in its component, while the other two arcs form a separate directed circuit. The degree conditions alone do not combine these routes into one trail.
Why Weak Connectivity, Not Strong Connectivity?
The condition is weak connectivity because a successful Euler trail need not make every vertex reachable from every other vertex by directed paths. In the first example, \(t\) has no outgoing arc, so it cannot reach any other vertex; nevertheless, the displayed trail uses every arc in order. The direction of each individual arc must be respected by the trail, but the connectivity test for the whole support ignores direction.
A common mistake is to require every vertex to have equal indegree and outdegree. That condition is appropriate for a closed directed Euler trail, not an open one: an open trail has one extra departure at its start and one extra arrival at its end. Another mistake is to check the degree conditions but omit connectivity, as the disconnected example demonstrates.
Check Your Understanding
Use the degree conditions and weak connectivity condition to justify each answer.
- Let \(V=\{p,q,r\}\) and \(E=\{p\to q,q\to r\}\). Does this digraph have an open Euler trail from \(p\) to \(r\)? Give the degree differences.
- Why must the auxiliary arc in the sufficiency proof be distinguishable if an arc \(t\to s\) may already exist?
- Suppose every vertex is balanced and the support is weakly connected. What does the balanced-circuit lemma guarantee?
- Explain why a directed Euler trail implies weak connectivity of the support even if it does not imply strong connectivity.
- Give a reason that degree balance at every vertex cannot hold for an open Euler trail with distinct endpoints.