AFTD Auto-Formalizing Theoretical Domains

mixed_graph_is_valid_directed_triangle

theoremverified

Sanity check: the directed triangle is a mixed graph (no loops, no antiparallel arcs).

Statement

theorem mixed_graph_is_valid_directed_triangle :
    mixed_graph_is_valid (⊥ : SimpleGraph (Fin 3)) (fun x y => y = x + 1)
Source
Sanity lemma for mixed graphs, arXiv:2610.14110 (New mixed cages, bounds and computational results).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • mixed_graph_is_validA mixed graph on V: undirected edges E (a simple graph) and arcs A, with no loops and at most one edge or arc between two vertices (no…
Used by 1

The proof, explained

To show that the directed 3-cycle on Fin 3 with no undirected edges forms a valid mixed graph, we must verify that it has no self-loops, no antiparallel arcs, and no overlap with undirected edges. The first two conditions are checked by finite case exhaustion (decide) on Fin 3, and the third holds vacuously because the undirected edge relation is empty.

  1. The directed triangle on Fin 3 with empty undirected edges is a valid mixed graph.

    By definition, a mixed graph is valid if its directed edge relation A has no self-loops (∀ x, ¬ A x x), has no antiparallel arcs (∀ x y, A x y → ¬ A y x), and is disjoint from its undirected edge relation E (∀ x y, E.Adj x y → ¬ A x y). Here, the vertices are Fin 3, the directed relation is cyclic successor y = x + 1, and the undirected graph is the empty graph ⊥. The refine tactic provides a witness for each of the three conjunctions: the first two (irreflexivity and asymmetry) are verified by exhaustive computation on the finite domain Fin 3 using decide, while the third holds vacuously since the empty graph has no edges (h : ⊥.Adj x y is False, eliminated via h.elim).

    line 3

      refine ⟨by decide, by decide, fun _ _ h => h.elim⟩

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_is_valid_directed_triangle :    mixed_graph_is_valid (⊥ : SimpleGraph (Fin 3)) (fun x y => y = x + 1) := by  refine ⟨by decide, by decide, fun _ _ h => h.elim⟩
See it in the graphDiscuss this resultChallenge it