AFTD Auto-Formalizing Theoretical Domains

digraph_is_acyclic

def

A digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it is transitive.

Statement

def digraph_is_acyclic {V : Type*} (D : Digraph V) : Prop
Defined in
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 (acyclic digraph: no directed cycle).
Verified
13 Oct 2026
Axioms
none listed
Used by 21

Lean source view module on GitHub

/-- A digraph is acyclic when it has no directed cycle: no vertex reaches itself by a
nonempty directed walk. -/
def digraph_is_acyclic {V : Type*} (D : Digraph V) : Prop :=
  ∀ x, ¬ Relation.TransGen D.Adj x x
See it in the graphDiscuss this resultChallenge it