mixed_graph_has_cycle_directed_triangle
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
- mixed_graph_has_girth_directed_triangleSanity check: the directed triangle has girth 3.
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.
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.
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)⟩