AFTD Auto-Formalizing Theoretical Domains

trianglefree24_graph_regular_oriented

theoremverified

The explicit 24-vertex digraph is loopless, oriented and 7-outregular.

Statement

theorem trianglefree24_graph_regular_oriented :
    (∀ v : Fin 24, (Finset.univ.filter fun w => trianglefree24_graph.Adj v w).card = 7) ∧
    (∀ v : Fin 24, ¬ trianglefree24_graph.Adj v v) ∧
    (∀ u v : Fin 24, trianglefree24_graph.Adj u v → ¬ trianglefree24_graph.Adj v u)
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 digraph on 24 vertices is defined by a circulant adjacency rule modulo 24 with connection set $\{1, 4, 5, 9, 13, 17, 21\}$. After establishing that edge adjacency is decidable, the theorem is proved by finite exhaustion using the `decide` tactic, which directly evaluates the 7-out-regularity, looplessness, and asymmetry of edges across all vertices.

  1. The adjacency relation of the graph is decidable.

    For any vertices $u, v \in \mathrm{Fin}\;24$, adjacency is defined by the modular condition $(v + 24 - u) \bmod 24 \in \{1, 4, 5, 9, 13, 17, 21\}$. Since this is a finite check on explicit natural numbers, whether an edge exists between any two vertices can be decided algorithmically.

    lines 4–6

      intro u v
      unfold trianglefree24_graph
      infer_instance
  2. The digraph is 7-out-regular, loopless, and oriented. automation

    Because the vertex set $\mathrm{Fin}\;24$ is finite and adjacency is decidable, each part of the conjunction—that every vertex has out-degree 7, that no vertex has a self-loop, and that no two vertices have edges in both directions—is a decidable proposition. The `decide` tactic completes the proof by exhaustive computation over all 24 vertices and all $24 \times 24 = 576$ pairs of vertices.

    line 12

      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 : DecidableRel trianglefree24_graph.Adj := by  intro u v  unfold trianglefree24_graph  infer_instancetheorem trianglefree24_graph_regular_oriented :    (∀ v : Fin 24, (Finset.univ.filter fun w => trianglefree24_graph.Adj v w).card = 7) ∧    (∀ v : Fin 24, ¬ trianglefree24_graph.Adj v v) ∧    (∀ u v : Fin 24, trianglefree24_graph.Adj u v → ¬ trianglefree24_graph.Adj v u) := by  decide
See it in the graphDiscuss this resultChallenge it