AFTD Auto-Formalizing Theoretical Domains

digraph_safe17_structure

theoremverified

The displayed graph is oriented and seven-diregular, and every two distinct vertices have a common predecessor.

Statement

theorem digraph_safe17_structure :
    (∀ u, ¬ digraph_safe17_graph.Adj u u) ∧
    (∀ u v, digraph_safe17_graph.Adj u v → ¬ digraph_safe17_graph.Adj v u) ∧
    (∀ u, (Finset.univ.filter fun v => digraph_safe17_graph.Adj u v).card = 7) ∧
    (∀ v, (Finset.univ.filter fun u => digraph_safe17_graph.Adj u v).card = 7) ∧
    (∀ u v, u ≠ v → ∃ p, digraph_safe17_graph.Adj p u ∧ digraph_safe17_graph.Adj p v)
Source
Finite safe-cycle obstruction for OP-110; experiment 13260.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 4

The proof, explained

The theorem establishes five structural properties of a directed graph on 17 vertices: it has no self-loops, contains no 2-cycles (is an oriented graph), is 7-diregular (each in-degree and out-degree is 7), and any two distinct vertices share a common predecessor. Decidability of the adjacency relation is first registered as an instance, after which the entire statement is verified by finite exhaustive computation via the `decide` tactic.

  1. Adjacency between any two vertices in the graph is decidable.

    For any two vertices $u$ and $v$ in $\mathrm{Fin}\; 17$, unfolding the definition of the graph reveals that adjacency is defined by whether $(v - u) \in \{1, 2, 3, 5, 6, 7, 13\}$. Membership in this explicit finite set of natural numbers is decidable by standard typeclass resolution.

    lines 2–4

      intro u v
      unfold digraph_safe17_graph
      infer_instance
  2. The graph is loopless, asymmetric, 7-out-regular, 7-in-regular, and every pair of distinct vertices shares a common predecessor. automation

    Because $\mathrm{Fin}\; 17$ is a finite type and the adjacency relation was shown to be decidable, the entire conjunction of universally and existentially quantified statements is decidable. The `decide` tactic evaluates the proposition to true by finite exhaustive computation.

    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

private instance in504_safe17_decAdj_0 : DecidableRel digraph_safe17_graph.Adj := by  intro u v  unfold digraph_safe17_graph  infer_instancetheorem digraph_safe17_structure :    (∀ u, ¬ digraph_safe17_graph.Adj u u) ∧    (∀ u v, digraph_safe17_graph.Adj u v → ¬ digraph_safe17_graph.Adj v u) ∧    (∀ u, (Finset.univ.filter fun v => digraph_safe17_graph.Adj u v).card = 7) ∧    (∀ v, (Finset.univ.filter fun u => digraph_safe17_graph.Adj u v).card = 7) ∧    (∀ u v, u ≠ v → ∃ p, digraph_safe17_graph.Adj p u ∧ digraph_safe17_graph.Adj p v) := by  decide
See it in the graphDiscuss this resultChallenge it