AFTD Auto-Formalizing Theoretical Domains

trianglefree24_graph_no_directed_triangles

theoremverified

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.

  1. 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.

    lines 4–6

      intro u v
      unfold trianglefree24_graph
      infer_instance
  2. 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.

    line 11

      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

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
See it in the graphDiscuss this resultChallenge it