AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_four_triangles

theoremverified

The displayed graph contains the four explicit directed triangles on vertices 0,1,4; 2,3,6; 5,7,9; and 8,10,12.

Statement

theorem digraph_safe17_four_triangles :
    digraph_safe17_graph.Adj 0 1 ∧ digraph_safe17_graph.Adj 1 4 ∧ digraph_safe17_graph.Adj 4 0 ∧
    digraph_safe17_graph.Adj 2 3 ∧ digraph_safe17_graph.Adj 3 6 ∧ digraph_safe17_graph.Adj 6 2 ∧
    digraph_safe17_graph.Adj 5 7 ∧ digraph_safe17_graph.Adj 7 9 ∧ digraph_safe17_graph.Adj 9 5 ∧
    digraph_safe17_graph.Adj 8 10 ∧ digraph_safe17_graph.Adj 10 12 ∧ digraph_safe17_graph.Adj 12 8
Source
Finite safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem verifies that four explicit triples of vertices form directed triangles in the 17-vertex tournament graph `digraph_safe17_graph`. Adjacency $u \to v$ in this graph is defined by whether the modular difference $(v - u) \pmod{17}$ belongs to the connection set $\{1, 2, 3, 5, 6, 7, 13\}$. After establishing that this adjacency relation is decidable, the 12 required edge relations are verified simultaneously by direct finite computation using the `decide` tactic.

  1. Adjacency in `digraph_safe17_graph` is decidable for any two vertices.

    For arbitrary vertices $u$ and $v$ in $\mathrm{Fin}\;17$, unfolding the definition of `digraph_safe17_graph` reduces adjacency to checking whether the integer value of $v - u$ belongs to the explicit set $\{1, 2, 3, 5, 6, 7, 13\}$. Lean's typeclass resolution (`infer_instance`) synthesizes decidability of membership in this finite set.

    lines 1–4

    private instance in504_safe17_decAdj_3 : DecidableRel digraph_safe17_graph.Adj := by
      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. The graph contains the four specified directed triangles. automation

    Using the decidability of adjacency, the `decide` tactic checks the 12 edge conditions simultaneously by computing the modular difference $(v - u) \pmod{17}$ for each pair and verifying that it belongs to $\{1, 2, 3, 5, 6, 7, 13\}$: the edges of the first two triangles ($0 \to 1 \to 4 \to 0$ and $2 \to 3 \to 6 \to 2$) have differences $1, 3, 13$, and those of the last two triangles ($5 \to 7 \to 9 \to 5$ and $8 \to 10 \to 12 \to 8$) have differences $2, 2, 13$.

    lines 6–11

    theorem digraph_safe17_four_triangles :
        digraph_safe17_graph.Adj 0 1 ∧ digraph_safe17_graph.Adj 1 4 ∧ digraph_safe17_graph.Adj 4 0 ∧
        digraph_safe17_graph.Adj 2 3 ∧ digraph_safe17_graph.Adj 3 6 ∧ digraph_safe17_graph.Adj 6 2 ∧
        digraph_safe17_graph.Adj 5 7 ∧ digraph_safe17_graph.Adj 7 9 ∧ digraph_safe17_graph.Adj 9 5 ∧
        digraph_safe17_graph.Adj 8 10 ∧ digraph_safe17_graph.Adj 10 12 ∧ digraph_safe17_graph.Adj 12 8 := by
      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

private instance in504_safe17_decAdj_3 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_four_triangles :    digraph_safe17_graph.Adj 0 1 ∧ digraph_safe17_graph.Adj 1 4 ∧ digraph_safe17_graph.Adj 4 0 ∧    digraph_safe17_graph.Adj 2 3 ∧ digraph_safe17_graph.Adj 3 6 ∧ digraph_safe17_graph.Adj 6 2 ∧    digraph_safe17_graph.Adj 5 7 ∧ digraph_safe17_graph.Adj 7 9 ∧ digraph_safe17_graph.Adj 9 5 ∧    digraph_safe17_graph.Adj 8 10 ∧ digraph_safe17_graph.Adj 10 12 ∧ digraph_safe17_graph.Adj 12 8 := by  decide
See it in the graphDiscuss this resultChallenge it