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
- op744_dice6_has_cycle_sixThe relation (dice_graph 6).Adj has a directed simple cycle of length 6, has_directed_cycle (dice_graph 6).Adj 6.
- op744_dice11_has_directed_cycle_ge_twelveThere exists an integer k ≥ 12 such that has_directed_cycle (dice_graph 11).Adj k holds.
- op744_dice3_no_cycle_threeThe relation (dice_graph 3).Adj contains no directed simple cycle of length 3, that is, ¬ has_directed_cycle (dice_graph 3).Adj 3.
- op744_dice7_has_cycle_fourteenThe relation (dice_graph 7).Adj has a directed simple cycle of length 14, has_directed_cycle (dice_graph 7).Adj 14.
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))