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 nis decidable.
- Used by 1
- petrial_R_is_treeFor every natural number m, the graph R_m is a tree.
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