trianglefree24_graph_no_directed_triangles
The explicit 24-vertex digraph contains no directed triangle.
Statement
theorem trianglefree24_graph_no_directed_triangles :
∀ u v w : Fin 24, trianglefree24_graph.Adj u v →
trianglefree24_graph.Adj v w → trianglefree24_graph.Adj w u → False- Source
- Finite check for experiments 12542 and 12544.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- trianglefree24_graphThe cyclic digraph on 24 vertices with positive modular steps 1, 4, 5, 9, 13, 17 and 21.
The proof, explained
The theorem is verified by exhaustive finite computation. Because the digraph has 24 vertices and decidable adjacency, the assertion that it contains no directed triangle is a decidable proposition. The proof first constructs a decision procedure for adjacency by unfolding its definition to membership in a finite set of natural numbers, and then invokes `decide` to evaluate the claim over all triples of vertices.
Adjacency in `trianglefree24_graph` is decidable.
Given two vertices $u, v \in \text{Fin } 24$, we unfold the definition of `trianglefree24_graph` so that adjacency becomes membership of the expression $(v + 24 - u) \bmod 24$ in the explicit finite set $\{1, 4, 5, 9, 13, 17, 21\}$. Typeclass inference (`infer_instance`) synthesizes the decision procedure from decidable membership in finite sets of natural numbers.
intro u v unfold trianglefree24_graph infer_instance
There are no directed triangles in `trianglefree24_graph`. automation
Because the vertex set $\text{Fin } 24$ is finite and adjacency is decidable, the proposition stating that no triple of vertices $(u, v, w)$ satisfies $u \to v$, $v \to w$, and $w \to u$ is decidable. The `decide` tactic checks all $24^3 = 13{,}824$ triples by finite computation in the Lean kernel and confirms that no directed triangle exists.
decide
- The proof relies entirely on Lean's kernel computation (`decide`) to check all $24^3 = 13{,}824$ triples rather than giving a mathematical explanation of why no three differences sum to $0 \pmod{24}$.
- The configuration options `maxRecDepth` and `maxHeartbeats` are adjusted at the top of the file to accommodate the large number of reduction steps required during exhaustive evaluation.
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.
set_option maxRecDepth 200000set_option maxHeartbeats 0private instance trianglefree24_decAdj_no_directed_triangles : DecidableRel trianglefree24_graph.Adj := by intro u v unfold trianglefree24_graph infer_instancetheorem trianglefree24_graph_no_directed_triangles : ∀ u v w : Fin 24, trianglefree24_graph.Adj u v → trianglefree24_graph.Adj v w → trianglefree24_graph.Adj w u → False := by decide