How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
A finite digraph without isolated vertices has a directed Euler circuit if and only if it is weakly connected and every indegree equals the corresponding outdegree
Statement
Let be a finite digraph with no isolated vertices. Then has a directed Euler circuit if and only if its underlying undirected graph is connected and
for every vertex .
Facts & Assumptions
Given: A finite digraph with no isolated vertices.
A directed Euler circuit is a closed directed trail using every arc exactly once (Euler trails and Euler circuits in multigraphs and digraphs).
Weak connectivity means connectivity of the underlying undirected graph, and a loop contributes one to each directed degree (Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity).
Directed trails follow arc orientations and repeat no arc (Directed walks, trails, paths and cycles, and strong connectivity).
In a balanced finite digraph, a nonempty directed trail maximal under unused outgoing-arc extension is closed (In an even multigraph or balanced digraph, a trail maximal among unused incident edges returns to its start).
Arc-disjoint directed closed trails sharing a vertex can be spliced into one directed closed trail (Edge-disjoint closed trails sharing a vertex can be spliced into one closed trail).
Proof
A directed Euler circuit uses one incoming and one outgoing arc at each visit, so it gives equal indegree and outdegree at every vertex. Because there are no isolated vertices and every arc lies on the circuit, all vertices lie in one connected underlying graph.
Conversely, suppose is weakly connected and balanced. The hypotheses and absence of isolated vertices provide an arc. Start with it, repeatedly extend at the terminal vertex by an unused outgoing arc, and stop when none remains. Finiteness gives termination, and [L1] makes the resulting trail closed.
Deleting the arcs of leaves equal residual indegree and outdegree at every vertex, because a closed directed trail uses equally many incoming and outgoing arcs there.
If an unused arc remains, take an underlying path from a vertex of toward an endpoint of an unused arc and stop at the first unused boundary arc incident with . If this arc points out of the incident vertex of , an unused outgoing arc is present there. If it points into that vertex, residual balance from step 2.1 supplies an unused outgoing arc there.
From that vertex, extend using residual outgoing arcs until maximal. By residual balance and [L1] the new trail closes, and [L2] splices it into .
Every splice uses at least one new arc. Finiteness therefore makes repetition of steps 2.1 through 3.1 terminate with one directed closed trail using every arc. This is a directed Euler circuit, and step 1.1 proves the converse necessity.
Depends on
- Euler trails and Euler circuits in multigraphs and digraphs
- Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity
- Directed walks, trails, paths and cycles, and strong connectivity
- In an even multigraph or balanced digraph, a trail maximal among unused incident edges returns to its start
- Edge-disjoint closed trails sharing a vertex can be spliced into one closed trail
Used by
Nothing in the library uses this result yet.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 21 results over 15 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Richard Stanley, Algebraic Combinatorics (standard reference, not scraped)
- Applied Combinatorics, Directed Graphs (standard reference, not scraped)