mixed_graph_is_valid_directed_triangle
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
- vertex_disjoint_routing_exists_zeroWith
p = 0the disjoint-paths predicate holds, so it is not vacuously false.
- vertex_disjoint_routing_exists_zeroWith
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.
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).
refine ⟨by decide, by decide, fun _ _ h => h.elim⟩
- Because the undirected edge relation is the empty graph ⊥, the adjacency hypothesis ⊥.Adj x y is definitionally False, so the third condition is dispatched directly by ex falso quodlibet (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
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_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⟩