AFTD Auto-Formalizing Theoretical Domains

instDecidableRelPetrialRGraphAdj

instance

For every natural number m, adjacency between vertices in the graph R_m is decidable.

Statement

instance instDecidableRelPetrialRGraphAdj (m : ℕ) : DecidableRel (petrial_R_graph m).Adj
Defined in
arXiv:2611.07503 Section 3
Verified
08 Nov 2026
Axioms
none listed
Built on 2
  • petrial_R_graphFor any natural number m, R_m is the simple graph on the vertex type Option (Fin m × Fin 5) obtained by connecting a root vertex none to…
  • inst_decidableRel_pathGraphAdjacency in the path graph pathGraph n is decidable.
Used by 1

Read back from the Lean

For any natural number $m$, the adjacency relation of the graph petrial_R_graph m (on the vertex type Option (Fin m × Fin 5)) is decidable; that is, for all vertices $a, b : \text{Option} (\text{Fin } m \times \text{Fin } 5)$, the relation (petrial_R_graph m).Adj a b is decidable.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Decidability of adjacency in the graph R_m. -/
instance instDecidableRelPetrialRGraphAdj (m : ℕ) : DecidableRel (petrial_R_graph m).Adj := by
  intro a b
  change Decidable (match a, b with
    | none, none => False
    | none, some (_, v) => v = 2
    | some (_, v), none => v = 2
    | some (i₁, v₁), some (i₂, v₂) => i₁ = i₂ ∧ (SimpleGraph.pathGraph 5).Adj v₁ v₂)
  match a, b with
  | none, none => exact isFalse False.elim
  | none, some (i, v) => infer_instance
  | some (i, v), none => infer_instance
  | some (i₁, v₁), some (i₂, v₂) => infer_instance
See it in the graphDiscuss this resultChallenge it