AFTD Auto-Formalizing Theoretical Domains

digraph_is_eulerian_orientation

def

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

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
See it in the graphDiscuss this resultChallenge it