mixed_graph_has_girth_directed_triangle
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
- mixed_graph_has_girthA mixed graph has girth g: it has a cycle of length g and no shorter cycle.
- mixed_graph_has_cycle_directed_triangleSanity check: the directed triangle 0 → 1 → 2 → 0 has a 3-cycle.
- 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…
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.
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.
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.
- In this development, `mixed_graph_has_cycle` requires $3 \le t$ by definition, so cycles of length 1 or 2 are ruled out purely by arithmetic without needing to check the edge relations.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩