Balance and Connectivity in a Digraph
In an undirected graph, degree balance and connectedness help characterize Euler circuits. In a digraph, the relevant balance is local and directional: at each vertex, the number of edges entering must equal the number leaving. Connectivity, by contrast, is tested after forgetting the directions. This distinction leads to a complete criterion for when every directed edge can be used exactly once in a closed route.
Throughout, a digraph is finite and has no loops or multiple directed edges; opposite arcs \(u\to v\) and \(v\to u\), if both present, are distinct edges. A directed walk follows each edge in its indicated direction. A directed trail is a directed walk with no repeated edge, and it is closed when its first and last vertices agree. An Euler circuit is a closed directed trail that uses every edge exactly once.
Connectivity here does not mean that every vertex can reach every other by following directed edges. It is ordinary connectivity after directions are forgotten. The theorem will show that, when balance also holds, this weaker-looking condition is enough.
Why Both Conditions Are Necessary
Proof. Let the Euler circuit have vertex sequence \(v_0,v_1,\dots,v_m\), where \(v_m=v_0\) and \(m\) is the number of edges. Each time the circuit arrives at a vertex, it also leaves it; this includes the starting vertex because the route is closed. Since every edge is used exactly once, the number of arrivals at \(v\) is \(d^-(v)\), and the number of departures is \(d^+(v)\). Thus \(d^-(v)=d^+(v)\) for every \(v\). Also, every non-isolated vertex occurs on the circuit, as it is an endpoint of an edge used there. The portion of the circuit between any two vertices on it gives a route between them; forgetting directions gives a connection in the underlying graph. Therefore all non-isolated vertices are connected. \(\square\)
Balance is required at every vertex, not merely as an equality between the total number of edges entering the whole graph and the total leaving it. Those totals are equal in every digraph, since each edge contributes one to each total. What matters is that the two counts agree separately at each vertex.
The Directed Euler-Circuit Criterion
Proof. The forward direction is the proposition. For the converse, suppose the non-isolated vertices are connected in the underlying graph and \(d^-(v)=d^+(v)\) at every vertex. We construct a closed directed trail and then enlarge it until it uses every edge.
Choose a vertex \(s\) with an outgoing edge and begin following unused outgoing edges from \(s\), stopping only when the current vertex has no unused outgoing edge. No edge is repeated, and the digraph is finite, so this process stops. The resulting trail must end at \(s\). Indeed, suppose it instead ends at \(t\ne s\). Along a trail from \(s\) to \(t\), the number of used outgoing edges minus used incoming edges at \(t\) is \(-1\): there is one more used arrival than departure there. Since the total outgoing and incoming counts at \(t\) are equal, the number of unused outgoing edges minus unused incoming edges at \(t\) is \(1\). In particular, an unused outgoing edge remains at \(t\), contradicting the stopping rule. Thus the trail is closed; call it \(C\).
If \(C\) uses every edge, it is an Euler circuit. Otherwise, consider the vertices appearing on \(C\). There must be an unused edge incident with one of them. To see this, take an endpoint of any unused edge and a path in the underlying graph from a vertex of \(C\) to that endpoint. If the endpoint is not already on \(C\), the first edge of the path that leaves the vertices of \(C\) cannot have been used: every used edge has both endpoints on \(C\). So that first edge is an unused edge incident with a vertex of \(C\). If the endpoint was already on \(C\), the chosen unused edge itself has this property.
At a vertex \(x\) of \(C\) incident with an unused edge, the unused edges have equal indegree and outdegree. The closed trail \(C\) used the same number of edges entering and leaving \(x\), so removing its used edges from the original digraph preserves the equality at \(x\) (and at every vertex). Consequently, if the unused edge incident with \(x\) enters \(x\), there is also an unused outgoing edge there; if it leaves \(x\), one is already available. Starting at \(x\), follow unused outgoing edges in the remaining digraph until none is available. The same endpoint argument, using the balance of the remaining edges, proves that this trail closes at \(x\).
Insert this new closed trail into \(C\) at \(x\). The result is still a closed directed trail: it follows \(C\) to \(x\), makes the new closed excursion back to \(x\), and then continues along \(C\). It uses no edge twice, and it uses strictly more edges than \(C\). If edges still remain, repeat this process. Each repetition adds at least one previously unused edge, and there are finitely many edges. The process therefore ends with a closed trail using every edge exactly once, which is an Euler circuit. \(\square\)
This proof is also a construction method: build a closed trail, find a vertex on it with unused outgoing edges, build another closed trail from that vertex, and splice the trails together. The underlying connectivity condition guarantees an attachment point whenever unused edges remain.
Worked Examples
Worked Example: Joining Two Closed Trails
Let \(V=\{a,b,c,d,e\}\) and \(E=\{a\to b,b\to c,c\to a,a\to d,d\to e,e\to a\}\). Determine whether this digraph has an Euler circuit and construct one.
The indegree and outdegree counts are as follows. At \(a\), the outgoing edges are \(a\to b,a\to d\), so \(d^+(a)=2\); the incoming edges are \(c\to a,e\to a\), so \(d^-(a)=2\). At \(b\), \(d^+(b)=1\) from \(b\to c\) and \(d^-(b)=1\) from \(a\to b\). At \(c\), \(d^+(c)=1\) from \(c\to a\) and \(d^-(c)=1\) from \(b\to c\). At \(d\), \(d^+(d)=1\) from \(d\to e\) and \(d^-(d)=1\) from \(a\to d\). At \(e\), \(d^+(e)=1\) from \(e\to a\) and \(d^-(e)=1\) from \(d\to e\). The underlying graph is connected: each of \(b,c,d,e\) is connected to \(a\). The theorem applies.
Here is the trail construction, choosing the available edges in the displayed order.
| Step | Edge used | Trail so far | Unused edges |
|---|---|---|---|
| Start | — | \(a\) | All six edges |
| 1 | \(a\to b\) | \(a,b\) | \(b\to c,c\to a,a\to d,d\to e,e\to a\) |
| 2 | \(b\to c\) | \(a,b,c\) | \(c\to a,a\to d,d\to e,e\to a\) |
| 3 | \(c\to a\) | \(a,b,c,a\) | \(a\to d,d\to e,e\to a\) |
| 4 | \(a\to d\) | \(a,b,c,a,d\) | \(d\to e,e\to a\) |
| 5 | \(d\to e\) | \(a,b,c,a,d,e\) | \(e\to a\) |
| 6 | \(e\to a\) | \(a,b,c,a,d,e,a\) | None |
The first three edges make a closed trail \(a,b,c,a\). The last three make another closed trail \(a,d,e,a\), which is joined at \(a\). The resulting circuit is \(a,b,c,a,d,e,a\).
Check: the sequence uses the edges \(a\to b,b\to c,c\to a,a\to d,d\to e,e\to a\), exactly the six edges in \(E\), each once, and ends at its starting vertex \(a\).
Worked Example: Balance Without Connectivity
Let \(V=\{1,2,3,4,5,6\}\) and \(E=\{1\to2,2\to3,3\to1,4\to5,5\to6,6\to4\}\). Each vertex has one incoming and one outgoing edge: for example, \(d^-(1)=1\) from \(3\to1\) and \(d^+(1)=1\) from \(1\to2\); the same count holds around each of the two directed triangles. Thus all six vertices are balanced.
But the underlying graph consists of two components, \(\{1,2,3\}\) and \(\{4,5,6\}\), with no edge between them. An Euler circuit cannot exist: a single route using edges from both components would have to move from one component to the other, and there is no edge allowing that move.
Check: the graph has six edges, three in each component. Any trail beginning in the first component stays there, so it cannot use the three edges in the second component. This confirms why balance alone is insufficient.
Worked Example: Connectivity Without Balance
Let \(V=\{1,2,3\}\) and \(E=\{1\to2,2\to3,3\to1,1\to3\}\). The underlying graph is connected: its edges join \(1\) to \(2\), \(2\) to \(3\), and \(1\) to \(3\). Now compute the directional degrees. At vertex \(1\), \(d^+(1)=2\) from \(1\to2,1\to3\), while \(d^-(1)=1\) from \(3\to1\). At vertex \(2\), \(d^+(2)=1\) and \(d^-(2)=1\). At vertex \(3\), \(d^+(3)=1\) from \(3\to1\), while \(d^-(3)=2\) from \(2\to3,1\to3\). Balance fails at \(1\) and \(3\), so the theorem rules out an Euler circuit.
Check: there are four edges, so the sum of all outdegrees is \(2+1+1=4\), and the sum of all indegrees is \(1+1+2=4\). The totals match, but the vertex-by-vertex counts do not. An Euler circuit would require two departures and two arrivals at vertex \(1\), not two departures and one arrival.
Common Pitfalls and What the Criterion Gives
Do not replace local balance by equality of totals. In the last example, total indegree equals total outdegree because every edge has one head and one tail. That equality holds for any digraph and does not imply an Euler circuit. Check \(d^-(v)=d^+(v)\) separately for every vertex.
Do not require directed reachability as an extra hypothesis. The theorem asks for connectedness in the underlying graph, not strong connectivity as a separate condition. Strong connectivity means that for every ordered pair of vertices there is a directed path from the first to the second. The criterion does not assume it; balance together with underlying connectivity is sufficient, as the proof constructs a circuit that visits every edge.
The hypothesis that the digraph has at least one edge avoids treating a graph with no edges as a meaningful Euler-circuit case here. Vertices incident with no edges do not participate in any edge-using route, so connectivity is tested only among non-isolated vertices. These qualifications matter: requiring every vertex to lie in one connected component would incorrectly exclude a digraph with an Euler circuit merely because it also has isolated vertices.
Check Your Understanding
Use the criterion and its proof to answer the following questions.
- Let \(V=\{p,q,r\}\) and \(E=\{p\to q,q\to r,r\to p,p\to r,r\to q,q\to p\}\). Verify the degree balance and underlying connectivity, then give an Euler circuit.
- Explain why an Euler circuit forces equal indegree and outdegree at each vertex, including its starting vertex.
- In the proof of sufficiency, why must a maximal trail of unused edges from \(s\) end at \(s\) rather than at a different vertex?
- Give a digraph with balanced indegrees and outdegrees but no Euler circuit, and identify which condition fails.
- Why does an unused edge incident with a vertex on a closed trail guarantee that an unused outgoing edge is available there?