digraph_safe17_four_triangles
The displayed graph contains the four explicit directed triangles on vertices 0,1,4; 2,3,6; 5,7,9; and 8,10,12.
Statement
theorem digraph_safe17_four_triangles :
digraph_safe17_graph.Adj 0 1 ∧ digraph_safe17_graph.Adj 1 4 ∧ digraph_safe17_graph.Adj 4 0 ∧
digraph_safe17_graph.Adj 2 3 ∧ digraph_safe17_graph.Adj 3 6 ∧ digraph_safe17_graph.Adj 6 2 ∧
digraph_safe17_graph.Adj 5 7 ∧ digraph_safe17_graph.Adj 7 9 ∧ digraph_safe17_graph.Adj 9 5 ∧
digraph_safe17_graph.Adj 8 10 ∧ digraph_safe17_graph.Adj 10 12 ∧ digraph_safe17_graph.Adj 12 8- 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
- monotone_cycle_three_adj_zero_oneIn the monotone cycle MC_3 on Fin 3, vertices 0 and 1 are adjacent.
The proof, explained
The theorem verifies that four explicit triples of vertices form directed triangles in the 17-vertex tournament graph `digraph_safe17_graph`. Adjacency $u \to v$ in this graph is defined by whether the modular difference $(v - u) \pmod{17}$ belongs to the connection set $\{1, 2, 3, 5, 6, 7, 13\}$. After establishing that this adjacency relation is decidable, the 12 required edge relations are verified simultaneously by direct finite computation using the `decide` tactic.
Adjacency in `digraph_safe17_graph` is decidable for any two vertices.
For arbitrary vertices $u$ and $v$ in $\mathrm{Fin}\;17$, unfolding the definition of `digraph_safe17_graph` reduces adjacency to checking whether the integer value of $v - u$ belongs to the explicit set $\{1, 2, 3, 5, 6, 7, 13\}$. Lean's typeclass resolution (`infer_instance`) synthesizes decidability of membership in this finite set.
private instance in504_safe17_decAdj_3 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instance
The graph contains the four specified directed triangles. automation
Using the decidability of adjacency, the `decide` tactic checks the 12 edge conditions simultaneously by computing the modular difference $(v - u) \pmod{17}$ for each pair and verifying that it belongs to $\{1, 2, 3, 5, 6, 7, 13\}$: the edges of the first two triangles ($0 \to 1 \to 4 \to 0$ and $2 \to 3 \to 6 \to 2$) have differences $1, 3, 13$, and those of the last two triangles ($5 \to 7 \to 9 \to 5$ and $8 \to 10 \to 12 \to 8$) have differences $2, 2, 13$.
theorem digraph_safe17_four_triangles : digraph_safe17_graph.Adj 0 1 ∧ digraph_safe17_graph.Adj 1 4 ∧ digraph_safe17_graph.Adj 4 0 ∧ digraph_safe17_graph.Adj 2 3 ∧ digraph_safe17_graph.Adj 3 6 ∧ digraph_safe17_graph.Adj 6 2 ∧ digraph_safe17_graph.Adj 5 7 ∧ digraph_safe17_graph.Adj 7 9 ∧ digraph_safe17_graph.Adj 9 5 ∧ digraph_safe17_graph.Adj 8 10 ∧ digraph_safe17_graph.Adj 10 12 ∧ digraph_safe17_graph.Adj 12 8 := by decide
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_3 : DecidableRel digraph_safe17_graph.Adj := by intro u v unfold digraph_safe17_graph infer_instancetheorem digraph_safe17_four_triangles : digraph_safe17_graph.Adj 0 1 ∧ digraph_safe17_graph.Adj 1 4 ∧ digraph_safe17_graph.Adj 4 0 ∧ digraph_safe17_graph.Adj 2 3 ∧ digraph_safe17_graph.Adj 3 6 ∧ digraph_safe17_graph.Adj 6 2 ∧ digraph_safe17_graph.Adj 5 7 ∧ digraph_safe17_graph.Adj 7 9 ∧ digraph_safe17_graph.Adj 9 5 ∧ digraph_safe17_graph.Adj 8 10 ∧ digraph_safe17_graph.Adj 10 12 ∧ digraph_safe17_graph.Adj 12 8 := by decide