digraph_is_eulerian_orientation
For a simple graph G and a digraph D on the vertex type Fin n (as for digraph_arborescence_count_at), D is an Eulerian orientation of G: is_graph_orientation G D holds, and at every vertex v the out-degree #{w | D.Adj v w} equals the in-degree #{w | D.Adj w v}, both counted with Finset.univ.filter.
Statement
def digraph_is_eulerian_orientation {n : ℕ} (G : SimpleGraph (Fin n)) (D : Digraph (Fin n)) [DecidableRel D.Adj] : Prop
- Defined in
- arXiv:2610.25886 (Extremal arborescences in graph orientations), Sec. 1 (Eulerian orientations)
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
- Used by 3
- digraph_eulerian_orientation_arborescence_count_posAn Eulerian orientation D of a finite connected simple graph is strongly connected, so for every root r it has at least one spanning…
- digraph_is_eulerian_orientation_of_alternatingAn alternating orientation (for any rotation system) is Eulerian: around each vertex σ maps outgoing darts bijectively to incoming ones…
- digraph_eulerian_orientation_reversalThe reversal of an Eulerian orientation of a simple graph is also an Eulerian orientation.
Read back from the Lean
The definition digraph_is_eulerian_orientation G D states that for a natural number n, a simple graph G on vertices Fin n, and a directed graph D on Fin n with decidable adjacency:
1. D is an orientation of G (via is_graph_orientation G D), meaning:
- for all vertices u, v : Fin n, D.Adj u v ∨ D.Adj v u holds if and only if G.Adj u v, and
- for all vertices u, v : Fin n, D.Adj u v and D.Adj v u do not both hold;
2. For every vertex v : Fin n, the out-degree of v in D (the cardinality of {w : Fin n | D.Adj v w}) is equal to the in-degree of v in D (the cardinality of {w : Fin n | D.Adj w v}).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- D is an Eulerian orientation of G: in-degree equals out-degree at every vertex. -/ def digraph_is_eulerian_orientation {n : ℕ} (G : SimpleGraph (Fin n)) (D : Digraph (Fin n)) [DecidableRel D.Adj] : Prop := is_graph_orientation G D ∧ ∀ v, (Finset.univ.filter (fun w => D.Adj v w)).card = (Finset.univ.filter (fun w => D.Adj w v)).card