AFTD Auto-Formalizing Theoretical Domains

mixed_graph_has_girth_directed_triangle

theoremverified

Sanity check: the directed triangle has girth 3.

Statement

theorem mixed_graph_has_girth_directed_triangle :
    mixed_graph_has_girth (⊥ : SimpleGraph (Fin 3)) (fun x y => y = x + 1) 3
Source
Sanity lemma for mixed-graph girth, arXiv:2610.14110 (New mixed cages, bounds and computational results).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

A mixed graph has girth 3 if it has a cycle of length 3 and no cycle of length strictly less than 3. The existence of a 3-cycle is given by `mixed_graph_has_cycle_directed_triangle`. The nonexistence of shorter cycles is immediate because `mixed_graph_has_cycle` requires $3 \le t$ by definition, which contradicts $t < 3$ by linear integer arithmetic.

  1. The directed triangle has girth 3: it contains a 3-cycle and no cycle of length less than 3.

    The definition of `mixed_graph_has_girth` requires showing two conjuncts: that a cycle of length 3 exists, and that no cycle has length $t < 3$. The first conjunct is supplied by `mixed_graph_has_cycle_directed_triangle`. For the second, suppose for contradiction that there is a cycle of length $t < 3$ (hypotheses `ht : t < 3` and `h : mixed_graph_has_cycle ... t`). By definition, a cycle must have length at least 3, so `h.1` yields $3 \le t$. Linear integer arithmetic (`omega`) detects the contradiction between $t < 3$ and $3 \le t$, closing the goal.

    line 3

    uses mixed_graph_has_cycle_directed_triangle

      ⟨mixed_graph_has_cycle_directed_triangle, fun _ ht h => by have := h.1; omega⟩
mixed_graph_has_cycle_directed_triangle
The mixed graph on vertex set `Fin 3` with no undirected edges and cyclic directed edges $y = x + 1$ has a cycle of length 3.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. 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_girth_directed_triangle :    mixed_graph_has_girth (⊥ : SimpleGraph (Fin 3)) (fun x y => y = x + 1) 3 :=  ⟨mixed_graph_has_cycle_directed_triangle, fun _ ht h => by have := h.1; omega⟩
See it in the graphDiscuss this resultChallenge it