digraph_has_digirth_ge
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
- not_digraph_ckk_subdivision_three_exceptionalThe statement
digraph_ckk_subdivision_three_exceptionalis false: The statement omits any nonemptiness hypothesis on the vertex type, so…
- not_digraph_ckk_subdivision_three_exceptionalThe statement
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