AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_rooted_four_unsafe

theoremverified

Every directed four-cycle through zero in the displayed graph has an outside vertex pointing to at least three of its vertices.

Statement

theorem digraph_safe17_rooted_four_unsafe :
    ∀ a b c : Fin 17,
      digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b →
      digraph_safe17_graph.Adj b c → digraph_safe17_graph.Adj c 0 →
      ∃ x : Fin 17, x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧
        ((digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧
          digraph_safe17_graph.Adj x b) ∨
         (digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧
          digraph_safe17_graph.Adj x c) ∨
         (digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x b ∧
          digraph_safe17_graph.Adj x c) ∨
         (digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧
          digraph_safe17_graph.Adj x c))
Source
Finite safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1
  • digraph_safe17_four_unsafeEvery directed four-cycle in the displayed graph has an outside vertex pointing to at least three of its vertices.

The proof, explained

The theorem is proved by finite computational exhaustion. Adjacency in the 17-vertex Cayley digraph is first established to be decidable. Because the vertex set Fin 17 is finite, the statement that every directed four-cycle through 0 is dominated at three or more vertices by an outside vertex is a decidable proposition, which Lean verifies by exhaustive evaluation using the `decide` tactic.

  1. The adjacency relation of digraph_safe17_graph is decidable.

    For any two vertices u and v, the graph definition is unfolded to express adjacency as (v - u).val ∈ {1, 2, 3, 5, 6, 7, 13}. Since membership in this explicit finite set of natural numbers is decidable, typeclass inference (`infer_instance`) automatically synthesises the decidability instance.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. Every directed four-cycle through 0 has an outside vertex pointing to at least three of its vertices. automation

    The theorem is a first-order sentence whose quantifiers range over Fin 17, a finite type with 17 elements. Because the adjacency relation is decidable, the entire formula is a decidable proposition. Lean's `decide` tactic evaluates this proposition by exhaustively checking all candidate four-cycles through 0 and verifying that each admits an outside vertex pointing to at least three vertices of the cycle.

    line 19

    uses in504_safe17_decAdj_2

      decide
in504_safe17_decAdj_2
For any two vertices u and v in Fin 17, it is decidable whether there is a directed edge from u to v in digraph_safe17_graph.

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_2 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_rooted_four_unsafe :    ∀ a b c : Fin 17,      digraph_safe17_graph.Adj 0 a → digraph_safe17_graph.Adj a b →      digraph_safe17_graph.Adj b c → digraph_safe17_graph.Adj c 0 →      ∃ x : Fin 17, x ≠ 0 ∧ x ≠ a ∧ x ≠ b ∧ x ≠ c ∧        ((digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧          digraph_safe17_graph.Adj x b) ∨         (digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x a ∧          digraph_safe17_graph.Adj x c) ∨         (digraph_safe17_graph.Adj x 0 ∧ digraph_safe17_graph.Adj x b ∧          digraph_safe17_graph.Adj x c) ∨         (digraph_safe17_graph.Adj x a ∧ digraph_safe17_graph.Adj x b ∧          digraph_safe17_graph.Adj x c)) := by  decide
See it in the graphDiscuss this resultChallenge it