AFTD Auto-Formalizing Theoretical Domains

has_directed_cycle

def

A directed graph with adjacency relation Adj has a directed simple cycle of length k (with 3 ≤ k) if there exists an injective map c : Fin k → V such that Adj (c i) (c (finRotate k i)) for all i : Fin k.

Statement

def has_directed_cycle {V : Type*} (Adj : V → V → Prop) (k : ℕ) : Prop
Defined in
arXiv:2610.40321 Def 2
Verified
31 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

For a type V, a relation Adj : V → V → Prop, and a natural number k, has_directed_cycle Adj k asserts that 3 ≤ k and there exists an injective function c : Fin k → V such that for every i : Fin k, Adj (c i) (c (finRotate k i)) holds (that is, there exists a directed cycle of k distinct vertices in the directed graph with vertex set V and edge relation Adj).

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

/-- Existence of a simple directed cycle of length k in a digraph. -/
def has_directed_cycle {V : Type*} (Adj : V → V → Prop) (k : ℕ) : Prop := 3 ≤ k ∧ ∃ c : Fin k → V, Function.Injective c ∧ ∀ i : Fin k, Adj (c i) (c (finRotate k i))
See it in the graphDiscuss this resultChallenge it