trianglefree24_graph_every_arc_dominated
Every arc of the explicit 24-vertex digraph has a common in-neighbor.
Statement
theorem trianglefree24_graph_every_arc_dominated :
∀ u v : Fin 24, trianglefree24_graph.Adj u v →
∃ w, trianglefree24_graph.Adj w u ∧ trianglefree24_graph.Adj w v- Source
- Finite check for experiment 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 states that in a specific 24-vertex directed graph, every directed edge $(u, v)$ has a common in-neighbor $w$ satisfying $w \to u$ and $w \to v$. Because the vertex set $\text{Fin } 24$ is finite and the adjacency relation is defined by an explicit membership condition in a finite set of integers, the property is a decidable proposition. The proof registers a decidability instance for graph adjacency and then verifies the universal statement by exhaustive computation using `decide`.
The adjacency relation on the 24-vertex digraph is decidable.
Given two vertices $u, v \in \text{Fin } 24$, we unfold the definition of `trianglefree24_graph`, which defines adjacency by $(v.val + 24 - u.val) \bmod 24 \in \{1, 4, 5, 9, 13, 17, 21\}$. Because membership in a finite set of natural numbers is decidable, typeclass synthesis (`infer_instance`) automatically provides the decision procedure, establishing that adjacency is a decidable relation (`DecidableRel`).
intro u v unfold trianglefree24_graph infer_instance
For every directed edge $(u, v)$, there exists a vertex $w$ that is a common in-neighbor of both $u$ and $v$. automation
Since the vertex set $\text{Fin } 24$ is finite and adjacency is decidable, the proposition $\forall u \, v, u \to v \implies \exists w, w \to u \land w \to v$ is decidable by bounded search. The `decide` tactic evaluates this finite check exhaustively and closes the goal.
decide
- The theorem is proved entirely by computational reflection: once adjacency is registered as decidable, the `decide` tactic verifies the claim by exhaustive evaluation over all vertices.
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_every_arc_dominated : DecidableRel trianglefree24_graph.Adj := by intro u v unfold trianglefree24_graph infer_instancetheorem trianglefree24_graph_every_arc_dominated : ∀ u v : Fin 24, trianglefree24_graph.Adj u v → ∃ w, trianglefree24_graph.Adj w u ∧ trianglefree24_graph.Adj w v := by decide