AFTD Auto-Formalizing Theoretical Domains

mixed_graph_has_cycle_directed_triangle

theoremverified

Sanity check: the directed triangle 0 → 1 → 2 → 0 has a 3-cycle.

Statement

theorem mixed_graph_has_cycle_directed_triangle :
    mixed_graph_has_cycle (⊥ : SimpleGraph (Fin 3)) (fun x y => y = x + 1) 3
Source
Sanity lemma for mixed-graph cycles, arXiv:2610.14110 (New mixed cages, bounds and computational results).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • mixed_graph_has_cycleA mixed graph has a cycle of length t ≥ 3: distinct vertices x_0, ..., x_{t-1} such that each x_i is joined to x_{i+1} (indices mod t) by…
Used by 1

The proof, explained

The theorem is proven by directly supplying the witness for the definition of a mixed graph cycle of length 3. Reflexivity gives 3 ≤ 3, the identity function on Fin 3 provides the required injective sequence of vertices, and each step along the cycle is a directed arc because the cyclic rotation permutation on Fin 3 maps i to i + 1.

  1. The empty graph on Fin 3 equipped with directed edges x → x + 1 contains a cycle of length 3.

    By definition, a mixed graph contains a cycle of length t if 3 ≤ t and there exists an injective sequence of vertices x : Fin t → V such that successive vertices under cyclic rotation are connected by an undirected edge or a directed arc. Here t = 3, so 3 ≤ 3 holds by reflexivity (le_rfl). We take x to be the identity function on Fin 3, which is injective by Function.injective_id. For every index i ∈ Fin 3, the successor index finRotate 3 i equals i + 1 by finRotate_apply, which matches the directed arc relation id (finRotate 3 i) = id i + 1, thereby proving the right disjunct of the edge condition via Or.inr.

    line 3

    uses le_rfl, Function.injective_id, Or.inr, finRotate_apply

      ⟨le_rfl, id, Function.injective_id, fun i => Or.inr (finRotate_apply i)⟩
le_rfl
The inequality relation ≤ is reflexive: a ≤ a for any element a in a preorder.
Function.injective_id
The identity function on any type is injective.
Or.inr
If proposition b holds, then the disjunction a ∨ b holds (right introduction for disjunction).
finRotate_apply
The cyclic rotation permutation on Fin n maps each element i to i + 1.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem mixed_graph_has_cycle_directed_triangle :    mixed_graph_has_cycle (⊥ : SimpleGraph (Fin 3)) (fun x y => y = x + 1) 3 :=  ⟨le_rfl, id, Function.injective_id, fun i => Or.inr (finRotate_apply i)⟩
See it in the graphDiscuss this resultChallenge it