AFTD Auto-Formalizing Theoretical Domains

trianglefree24_graph_every_arc_dominated

theoremverified

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

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

    lines 4–6

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

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