Motivation
A one-way road can be traversed in only one direction. Treating it as an undirected edge may incorrectly suggest that a return trip exists. Directed graphs make this asymmetry explicit. We first separate the two common notions of connectivity, then prove exactly when every directed edge can be traversed once in a closed route.
Definitions
Definition 5.1.1
(Directed graphs, walks and connectivity)
A finite directed graph has a finite vertex set and a finite set of ordered edges , called arcs. For this section, loops and parallel arcs are excluded; arcs in both directions between two distinct vertices are permitted. The out-degree counts arcs leaving , and the in-degree counts arcs entering it.
A directed walk follows every arc in its specified direction; a directed path is a directed walk without repeated vertices. A directed trail does not repeat an arc. A vertex reaches itself by a length-zero path. The graph is strongly connected if every vertex reaches every other vertex. It is weakly connected if the undirected graph obtained by forgetting arc directions is connected. Strong connectivity implies weak connectivity; the converse fails, for example on the single arc .
Definition 5.1.2
(Directed Euler circuit)
A directed Euler circuit is a closed directed trail using every arc exactly once. Vertices of total degree zero are isolated. As in the undirected case, we check connectivity only on vertices incident with arcs. For a graph with no arcs and at least one vertex, we allow a length-zero circuit; the main criterion below assumes at least one arc.
Theorem/proposition
Theorem 5.1.3
(Directed Euler circuit criterion)
A finite directed graph with at least one arc has a directed Euler circuit if and only if every vertex has and all vertices incident with arcs belong to one weakly connected component.
Theorem 5.1.4
(Balance turns weak connectivity into strong connectivity)
If a finite directed graph has equal in-degree and out-degree at every vertex and its non-isolated vertices are weakly connected, then those vertices are strongly connected.
Proof sketch or proof idea
Proof
(Pairing arrivals with departures, then splicing closed trails)
For necessity, a closed directed trail pairs each arrival at a vertex with the next departure; at its start, pair the final arrival with the initial departure. If it uses every arc exactly once, in-degree equals out-degree. Ignoring direction along the circuit gives a walk through all arc endpoints, so the non-isolated vertices are weakly connected.
For sufficiency, start at a non-isolated vertex and follow unused outgoing arcs until none remains. The resulting trail must end at its start. At any other vertex, the used incoming arcs outnumber the used outgoing arcs by one when the trail currently ends there. Since its original in-degree equals its out-degree, there must be an unused outgoing arc. Thus stopping at a different vertex is impossible.
If unused arcs remain, delete the current closed trail's arcs temporarily. At every vertex the deleted trail used equally many incoming and outgoing arcs, so the remaining directed graph is still balanced. There is a vertex on the current trail incident with an unused arc. Take a weak path from the trail to an endpoint of an unused arc. If the path contains an unused arc, its first such arc is incident with a trail vertex because every preceding arc lies on the trail. If the path uses only trail arcs, its endpoint is on the trail and is incident with the unused arc chosen at the outset. At that vertex, balance of remaining arcs implies that positive remaining in-degree is equivalent to positive remaining out-degree. Hence an unused outgoing arc exists. Start another unused-arc trail there; the same argument makes it close. Splice it into the current trail. Each splice consumes at least one new arc, so after finitely many splices all arcs have been used.
Proof X-ray
How residual balance permits splicing
Balance is used in two different places. In the walk-until-stuck step it is used at the current endpoint: a vertex other than the start has been entered once more than it has been left, so equal original degrees leave an unused outgoing arc. Only the start can absorb the final arrival, because its first departure has no matching arrival. In the splicing step balance is used for the residual graph: deleting a closed trail removes equally many incoming and outgoing arcs at every vertex, so the leftover arcs are balanced and the same walk-until-stuck argument produces another closed trail.
Weak connectivity is used only to find a vertex where the new closed trail touches the old one. It never supplies a direction; residual balance is what turns “incident with an unused arc” into “has an unused outgoing arc”. The process terminates because each splice uses at least one new arc. Without weak connectivity the splice vertex need not exist, as for two disjoint triangles; without balance the first trail can stop away from its start, as on .
Proof
(Reading a directed path off the circuit)
The second theorem now follows directly: an Euler circuit through all non-isolated vertices contains a directed segment from any one such vertex to any other. Removing repeated portions of that segment gives a directed path. Isolated vertices are excluded from the claim, because they cannot reach another vertex.
Worked examples
Worked example 5.1.5
(A directed triangle)
The arcs , , give every vertex one incoming and one outgoing arc. The route is a directed Euler circuit. It is also a directed Hamiltonian cycle in this particular example, although the two definitions ask for different things.
Worked example 5.1.6
(Weak connectivity without a return path)
For , the underlying undirected graph is connected, but cannot reach . The endpoints also fail balance: has out-degree 1 and in-degree 0, while has the opposite. There is no closed directed trail using both arcs.
Worked example 5.1.7
(Balanced but disconnected)
Take two disjoint directed triangles. Every vertex is balanced, but their non-isolated vertices lie in two weak components. No single directed trail can use arcs from both components. Thus balance without the connectivity condition is insufficient.
Common mistakes
Common mistake
(Reading weak connectivity as two-way travel)
Weak connectivity ignores arrow directions; it does not generally imply the ability to travel both ways. On the underlying graph is connected but reaches nothing. The implication to strong connectivity above relies on degree balance at every vertex.
Common mistake
(Checking total balance instead of balance at every vertex)
Equality of the total in-degree and total out-degree is automatic in every finite directed graph, because each arc contributes once to each total. It does not imply equality at each individual vertex, which is what the criterion requires.
Common mistake
(Confusing Euler circuits with Hamiltonian cycles)
An Euler circuit concerns arcs, whereas a Hamiltonian cycle concerns vertices. A circuit may revisit vertices while using distinct arcs. A directed graph with two directed triangles sharing only one vertex has an Euler circuit through both triangles but no Hamiltonian cycle: deleting the shared vertex disconnects the underlying graph.
Counterexample mode
Strong connectivity does not replace balance
Claim: a strongly connected directed graph has a directed Euler circuit, since every arc can be reached and then left. Take the arcs , , and . The cycle makes the graph strongly connected. But and , while and . A closed trail using all four arcs would leave twice and enter it only once, which is impossible. Indeed the trail uses every arc and is stuck at , whose only outgoing arc is spent. The criterion needs balance at every vertex; strong connectivity is a consequence of balance and weak connectivity, not a substitute for balance.
Summary
Balance is a local condition at every vertex; weak connectivity of the non-isolated subgraph is a global condition. Together they yield a closed route using all arcs, and consequently strong connectivity among non-isolated vertices. Without balance, weak and strong connectivity are different.
Exercises
Quick check
(A directed graph has arcs and , plus an isolated vertex . Does it have a directed Euler circuit under the stated convention?)
Decide which vertices the connectivity condition concerns.
Solution · Answer
Yes. The trail uses both arcs. The isolated vertex is excluded from the connectivity test because it has no arc to traverse.
Quick check
(A graph has arcs , and . Identify a failed Euler condition.)
Compute the in-degree and out-degree of each vertex.
Solution · Answer
Vertex has out-degree and in-degree , so balance fails. The graph has no directed Euler circuit, even though the non-isolated underlying graph is connected.
Degree balance across a cut
For any subset , let be the number of arcs from to its complement and the number entering from its complement.
Lemma 5.1.8
(Cut balance identity)
In every finite directed graph, for every ,
In particular, if every vertex is balanced, then for every .
Proof
(Arcs inside cancel)
Sum over the vertices and sort the arcs by the position of their endpoints. An arc with both endpoints in contributes at its tail and at its head, and cancels. An arc leaving contributes at its tail only, an arc entering contributes at its head only, and an arc with no endpoint in contributes nothing. The total is therefore .
When every vertex is balanced, every vertex subset has equally many arcs entering and leaving. This identity is another way to understand why a balanced directed graph cannot have a one-way bottleneck between groups. It does not by itself rule out disconnected groups, which is why the weak-connectivity assumption remains necessary.
For a finite directed graph, reachability is an equivalence relation after requiring it in both directions. Its classes are the strong components. Contract each strong component to a single vertex, retaining arcs between distinct components. The resulting condensation is a directed acyclic graph: a directed cycle of distinct components would make every component on it mutually reachable, so they should have been one component.
This yields an independent proof that balance plus weak connectivity implies strong connectivity on the non-isolated vertices.
Proof
(A second proof through the condensation)
First restrict to the subgraph induced by the non-isolated vertices; it remains balanced and is weakly connected by hypothesis. Form its condensation and suppose it had more than one vertex. Any finite directed acyclic graph has a source: start at any vertex and repeatedly follow an incoming arc; because there is no directed cycle and there are finitely many vertices, this process must stop at a vertex with no incoming arc. In a weakly connected condensation with more than one vertex, that source must have at least one outgoing arc. Let be the original vertices in its component. Then and , contradicting the cut-balance identity. Therefore there is only one strong component among non-isolated vertices.
This proof does not assume that a weak path has a consistent direction. It uses weak connectivity only after contraction to ensure the chosen source is incident to some arc, then uses balance to rule out all those arcs pointing outward. The case of a single non-isolated strong component is already the conclusion; a graph with no arcs is excluded from the theorem's non-isolated connectivity claim.
Quick check
(Let be a set of vertices in a balanced directed graph. If exactly three arcs leave , how many enter it?)
Apply the cut balance identity.
Solution · Answer
The cut balance identity gives . Arcs with both endpoints in do not affect the count.
Reachability and matrices
Index the vertices and define an adjacency matrix by when the arc exists, and zero otherwise.
Proposition 5.1.9
(Powers of the adjacency matrix count walks)
With this row-to-column convention, is the number of directed walks of length from to , for every nonnegative integer ; here counts length-zero walks.
Proof
(Induction on the walk length)
For the only walk from to of length zero exists exactly when , matching . Suppose the claim holds for . Then
Every walk of length from to splits uniquely into a walk of length from to its penultimate vertex , followed by the arc . The term for counts exactly those walks, so the sum counts all of them.
For example, the directed triangle has
The entry counts the walk ; because the two-step walk from 3 ends at 2. The matrix counts walks, not necessarily paths: a longer walk may repeat vertices or arcs. If a directed walk connects two vertices, removing portions between repeated occurrences of a vertex gives a directed path with the same endpoints.
Concept lensAlgebraic
Reachability as positivity of a matrix sum
Put . A path has length at most , every walk can be shortened to a path, and every path is a walk. Hence is reachable from exactly when , and distinct vertices are mutually reachable exactly when and . The graph is strongly connected exactly when every entry of is positive. A statement about the existence of routes becomes a sign condition on a computable integer matrix.
The entries are counts over the integers, not arithmetic modulo two: reducing modulo two can turn an even number of walks into zero and incorrectly suggest non-reachability. For example, two distinct length-two walks from to give integer entry 2, but entry 0 over .
Quick check
(In the directed triangle above, where does a length-four walk starting at end?)
Each vertex has exactly one outgoing arc.
Solution · Answer
After three steps it returns to , and one more step reaches . Thus ; there is exactly one choice at each step.
An open directed Euler trail
Theorem 5.1.10
(Directed Euler trail criterion)
Let a finite directed graph have at least one arc, and let be vertices. There is a directed trail from to using every arc exactly once if and only if , , every other vertex is balanced, and the non-isolated vertices are weakly connected.
Proof
(An auxiliary vertex closes the trail)
Suppose a directed trail uses every arc once and has distinct start and end . Pair arrivals with departures at all internal occurrences. At one departure is unpaired, and at one arrival is unpaired. Therefore
and every other vertex is balanced; ignoring directions along the trail shows that the non-isolated vertices are weakly connected. These conditions and weak connectivity on the non-isolated vertices are also sufficient. Add a new auxiliary vertex and arcs and . The augmented graph is balanced and its non-isolated vertices remain weakly connected, so it has a directed Euler circuit. Rotate the circuit to start at , and remove its first and last arcs. The remaining trail starts at , ends at , and uses each original arc once. The new vertex ensures the construction does not introduce a parallel arc when already exists.
The arcs then split into a least number of trails, equal to the total surplus of out-degree.
A path to generalization
What if balance fails at many vertices?
The arcs then split into a least number of trails, equal to the total surplus of out-degree.
Keep the non-isolated vertices weakly connected and put . An open trail changes the count only by at its start and at its end, so covering all arcs needs at least arc-disjoint trails. Conversely, pair surplus units with deficit units and, for each pair , add a fresh vertex with arcs . The enlarged graph satisfies the circuit criterion, and deleting the fresh vertices cuts its Euler circuit into exactly trails.
Quick check
(Determine whether , , , admit a directed Euler trail using all arcs, and provide one if they do.)
Find the vertices that are not balanced.
Solution · Answer
Vertices are balanced; has one extra outgoing arc and one extra incoming arc. The underlying non-isolated graph is connected. The trail uses all four arcs once, starting at and ending at . It cannot be a circuit because balance fails at those two endpoints.