digraph_safe17_rooted_triangle_unsafe
Every directed triangle through zero in the displayed graph has an outside vertex pointing to all three of its vertices.
Statement
theorem digraph_safe17_rooted_triangle_unsafe :
∀ a b : Fin 17,
digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b →
digraph_safe17_graph.Adj b 0 → ∃ x : Fin 17,
x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧
digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧
digraph_safe17_graph.Adj x b- Source
- Finite safe-cycle obstruction for OP-110; experiment 13260.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_safe17_graphThe seventeen-vertex cyclic digraph with the displayed seven out-steps.
- Used by 1
- digraph_safe17_triangle_unsafeEvery directed triangle in the displayed graph has an outside vertex pointing to all three of its vertices.
The proof, explained
The proof proceeds by exhaustive finite verification. First, it registers a decidability instance for the adjacency relation of the 17-vertex tournament. With decidability established, the theorem—a bounded first-order sentence over Fin 17—is closed automatically by the decide tactic via direct computational evaluation over all vertex tuples.
Adjacency in digraph_safe17_graph is decidable for all pairs of vertices.
We fix two arbitrary vertices u and v in Fin 17, unfold the definition of the graph to expose the edge condition (v - u).val ∈ {1, 2, 3, 5, 6, 7, 13}, and invoke Lean's typeclass synthesis (infer_instance) to conclude decidability of membership in this explicit finite set of natural numbers.
intro u v unfold digraph_safe17_graph infer_instance
Every directed triangle through 0 has an external common predecessor pointing to all three vertices. automation
Because Fin 17 is a finite domain and all relations and connectives in the statement are decidable, the proposition is decidable by exhaustive computation. The decide tactic verifies all 289 pairs (a, b) in Fin 17 × Fin 17: whenever 0 → a → b → 0 forms a directed triangle, it finds a suitable vertex x ∉ {0, a, b} pointing to 0, a, and b.
decide
- The auxiliary instance in504_safe17_decAdj_1 (lines 1–4) establishes decidability of the adjacency relation so that the kernel can evaluate adjacency queries computationally. The entire theorem is then verified by the decide tactic (line 13) via exhaustive finite search over Fin 17.
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.
private instance in504_safe17_decAdj_1 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_rooted_triangle_unsafe : ∀ a b : Fin 17, digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b → digraph_safe17_graph.Adj b 0 → ∃ x : Fin 17, x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧ digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b := by decide