Degree Balance in Directed Euler Trails

Why Direction Changes the Degree Test

In an undirected graph, each edge contributes to degree at both ends, and the parity of degrees constrains an Euler trail. In a directed graph, orientation matters: each vertex has a number of edges leaving it and a number entering it. An Euler trail must use every directed edge exactly once, so the trail’s first and last vertices account for any imbalance between these two counts. This gives a precise necessary condition, and it identifies the only possible endpoints of an open trail.

Throughout, a directed graph is finite and simple: its edges are directed, with no loops or repeated directed edges. Oppositely directed edges between the same two vertices are allowed. A directed walk is a sequence $v_0,v_1,\ldots,v_m$ in which each $v_{i-1}v_i$ is a directed edge pointing from $v_{i-1}$ to $v_i$. A directed trail is a directed walk with no repeated edge; vertices may repeat. An Euler trail is a directed trail that uses every edge of the graph exactly once. It is closed if its first and last vertices are the same, and open otherwise. A closed Euler trail is also called an Euler circuit.

Definition: The outdegree $d^+(v)$ of a vertex $v$ is the number of directed edges leaving $v$, and its indegree $d^-(v)$ is the number entering $v$. The degree difference is $d^+(v)-d^-(v)$. An edge directed from $u$ to $v$ contributes $1$ to $d^+(u)$ and $1$ to $d^-(v)$.

The signs in the difference are useful to remember: a vertex with one more departure than arrival has difference $+1$, while one with one more arrival than departure has difference $-1$. A trail that starts at $s$ and finishes at $t$ must have a net extra departure at $s$ and a net extra arrival at $t$, unless $s=t$, in which case the endpoint effects cancel.

The Degree-Balance Theorem

Theorem: Suppose a directed graph has an Euler trail $v_0,v_1,\ldots,v_m$, where $m$ is the number of edges and $v_0=s$, $v_m=t$. For every vertex $x$, $$ d^+(x)-d^-(x)= \begin{cases} 1 & \text{if }x=s\text{ and }s\ne t,\\ -1 & \text{if }x=t\text{ and }s\ne t,\\ 0 & \text{otherwise.} \end{cases} $$ In particular, an Euler circuit has $d^+(x)=d^-(x)$ at every vertex. An open Euler trail must start at the unique vertex with difference $+1$ and finish at the unique vertex with difference $-1$.

Proof. Fix any vertex $x$. For each step $i$ of the trail, the directed edge $v_{i-1}v_i$ contributes one departure from $x$ if $v_{i-1}=x$, and one arrival at $x$ if $v_i=x$. Since the trail uses every edge exactly once, counting these departures and arrivals along the trail gives the graph’s full outdegree and indegree. Therefore $$ d^+(x)-d^-(x) =\sum_{i=1}^{m}\bigl(\mathbf{1}_{v_{i-1}=x}-\mathbf{1}_{v_i=x}\bigr) =\mathbf{1}_{v_0=x}-\mathbf{1}_{v_m=x}, $$ where $\mathbf{1}_{P}$ is $1$ when statement $P$ holds and $0$ otherwise. The last equality follows by cancellation: every term for an internal position $v_i$, with $1\le i<m$, occurs once with a plus sign and once with a minus sign. If $s\ne t$, the expression is $1$ at $s$, $-1$ at $t$, and $0$ elsewhere. If $s=t$, the two endpoint contributions cancel at every vertex. This proves the stated conditions, including the length-zero case $m=0$, in which $s=t$ and all degree differences are zero. $\square$

The endpoint statement follows directly from the theorem: in an open Euler trail the start is the only vertex whose difference is $+1$, and the finish is the only vertex whose difference is $-1$. Thus, if a directed graph has an open Euler trail at all, its endpoints are forced by its degrees; choosing a different start or finish cannot produce such a trail.

There is also a useful consistency check. In any directed graph, the sum of all degree differences is zero: each directed edge contributes $+1$ at its tail and $-1$ at its head, so its total contribution is zero. For an open Euler trail the two nonzero differences, $+1$ and $-1$, agree with this identity.

Using the Conditions

Worked Example: Checking a Directed Euler Circuit

Let $G=(V,E)$ have $V=\{p,q,r,s\}$ and directed edges $E=\{pq,qp,pr,rs,sp\}$. The sequence $p,q,p,r,s,p$ is a candidate Euler circuit. Check its edges and the degree balance.

The sequence uses, in order, $pq,qp,pr,rs,sp$. These are exactly the five edges in $E$, each used once, and the sequence returns to $p$. It is therefore an Euler circuit.

Now count degrees. At $p$, the outgoing edges are $pq,pr$, so $d^+(p)=2$; the incoming edges are $qp,sp$, so $d^-(p)=2$. At $q$, the outgoing edge is $qp$ and the incoming edge is $pq$, giving $d^+(q)=1$ and $d^-(q)=1$. At $r$, the outgoing edge is $rs$ and the incoming edge is $pr$, giving $1$ and $1$. At $s$, the outgoing edge is $sp$ and the incoming edge is $rs$, also giving $1$ and $1$. Every difference is $0$, as required for a circuit.

Check: The circuit has five steps and uses five distinct edges, namely $pq,qp,pr,rs,sp$. The degree counts give total outdegree $2+1+1+1=5$ and total indegree $2+1+1+1=5$, each equal to $|E|=5$.

Worked Example: Finding the Endpoints of an Open Trail

Let $G=(V,E)$ have $V=\{a,b,c,d\}$ and directed edges $E=\{ab,bc,ca,ad\}$. Determine what the degree conditions say about an Euler trail, and check the sequence $a,b,c,a,d$.

At $a$, the outgoing edges are $ab,ad$, and the incoming edge is $ca$. Hence $d^+(a)=2$, $d^-(a)=1$, and the difference is $2-1=1$. At $b$, $ab$ enters and $bc$ leaves, giving difference $1-1=0$. At $c$, $bc$ enters and $ca$ leaves, also giving difference $1-1=0$. At $d$, $ad$ enters and no edge leaves, giving difference $0-1=-1$. Thus the only possible open-trail start is $a$, and the only possible finish is $d$.

The proposed sequence follows the directed edges $ab,bc,ca,ad$, in that order. It uses all four edges exactly once, begins at $a$, and ends at $d$, so it is an open Euler trail. Its endpoints match the degree test.

Check: The total outdegree is $2+1+1+0=4$, and the total indegree is $1+1+1+1=4$, matching the four edges. The trail has four steps, and its degree differences are $+1,0,0,-1$, as the theorem requires.

Worked Example: Rejecting a Degree Pattern

Let $G=(V,E)$ have $V=\{1,2,3,4\}$ and directed edges $E=\{12,13,24\}$. Can this graph have an Euler trail?

Vertex $1$ has two outgoing edges, $12$ and $13$, and no incoming edges, so its difference is $2-0=2$. Vertex $2$ has one outgoing edge, $24$, and one incoming edge, $12$, so its difference is $1-1=0$. Vertex $3$ has no outgoing edge and one incoming edge, $13$, so its difference is $0-1=-1$. Vertex $4$ has no outgoing edge and one incoming edge, $24$, so its difference is $0-1=-1$.

An open Euler trail requires exactly one difference $+1$, exactly one difference $-1$, and zero differences at all other vertices. A closed Euler trail requires all differences to be zero. Here the differences are $2,0,-1,-1$, which satisfy neither pattern. Therefore this graph has no Euler trail.

Check: The total outdegree is $2+1+0+0=3$, and the total indegree is $0+1+1+1=3$, as both totals must equal the three edges. The failure is not a counting-total error: it is the value $2$ at vertex $1$ and the two vertices with difference $-1$, which cannot arise from one trail’s endpoints.

What Degree Balance Does—and Does Not—Tell You

The theorem gives necessary conditions: every Euler trail must satisfy them. It is not a general sufficiency test. Equal indegree and outdegree at every vertex do not, by themselves, ensure that one trail can use every edge. For example, let $V=\{a,b,c,d\}$ and $E=\{ab,ba,cd,dc\}$. Each vertex has indegree $1$ and outdegree $1$, so all degree differences are zero. But a directed walk that starts among $a,b$ cannot reach either $c$ or $d$, because there is no edge between the two pairs. No single trail can use all four edges. The degree test is a first check, not a complete existence criterion.

For a proposed open Euler trail, check the direction and the endpoints carefully. The start must have one more outgoing edge than incoming edge; the finish must have one more incoming edge than outgoing edge. Reversing these signs reverses the claimed endpoints. For a proposed Euler circuit, every vertex must balance, because each arrival at a vertex is paired with a departure around the closed traversal.

Common Pitfalls

Counting visits instead of arrivals and departures. In the open-trail example, $a$ appears twice in the sequence $a,b,c,a,d$: once at the start and once internally. That does not mean its indegree and outdegree are equal. The actual edge count is $d^+(a)=2$, from $ab$ and $ad$, and $d^-(a)=1$, from $ca$, so the difference is $+1$. Internal appearances of a vertex pair an arrival with a later departure, but the starting and finishing positions do not both have such a pair.

Reversing the endpoint signs. A common incorrect conclusion is that a start must have one more incoming edge than outgoing edge. The formula shows the opposite: $d^+(s)-d^-(s)=1$. At the finish, the trail has the extra arrival, so $d^+(t)-d^-(t)=-1$.

Treating balance as a guarantee. Balanced degrees are required for a circuit, but the disconnected example above has balanced degrees and no Euler trail. A degree calculation can rule out a trail when the conditions fail and can identify endpoints when they hold; it cannot by itself establish that all edges can be traversed in one trail.

Check Your Understanding

Use the degree-balance identity to answer each question. When testing a proposed trail, check both the orientation and whether every edge is used exactly once.

For a directed Euler trail from $s$ to $t$, what are the degree differences at $s$, $t$, and every other vertex?
Can a directed Euler circuit contain a vertex with outdegree $3$ and indegree $2$? Explain.
A digraph has one vertex with difference $+1$, one with difference $-1$, and all others with difference $0$. What can you conclude about the possible endpoints, and what can you not yet conclude?
Prove that the sum of the degree differences over all vertices of any finite directed graph is zero.
Give a directed graph with all degree differences zero but no Euler trail, and explain why balance alone does not suffice.