AFTD Auto-Formalizing Theoretical Domains

digraph_has_digirth_ge

def

A digraph D has digirth at least g if every directed cycle of length at least 2 in D (represented by a list c of distinct vertices with 2 ≤ c.length that forms a directed chain in D whose last vertex has an arc to its first vertex) has length at least g.

Statement

def digraph_has_digirth_ge {V : Type*} (D : Digraph V) (g : ℕ) : Prop
Defined in
arXiv:2610.38574 Section 2.1
Verified
30 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a type V, a directed graph D : Digraph V, and a natural number g : ℕ, digraph_has_digirth_ge D g is the proposition that for every list c of vertices in V: if c has no duplicate elements (c.Nodup), has length at least 2 (2 ≤ c.length), forms a directed chain in D (c.IsChain D.Adj), and there exist vertices u, v : V such that u is the first element of c (c.head? = some u), v is the last element of c (c.getLast? = some v), and there is a directed edge from v to u (D.Adj v u), then g ≤ c.length. In other words, every simple directed cycle in D of length at least 2 has length at least g.

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

/-- A digraph has digirth at least g if every directed cycle of length at least 2 has length at least g. -/
def digraph_has_digirth_ge {V : Type*} (D : Digraph V) (g : ℕ) : Prop := ∀ c : List V, (c.Nodup ∧ 2 ≤ c.length ∧ c.IsChain D.Adj ∧
    ∃ u v, c.head? = some u ∧ c.getLast? = some v ∧ D.Adj v u) → g ≤ c.length
See it in the graphDiscuss this resultChallenge it