AFTD Auto-Formalizing Theoretical Domains

join_complete_turan_decidableRel

instance

Adjacency in the join graph G_a = K_a ∨ T_{r-1}(n-a) on vertex set Fin a ⊕ Fin (n - a) is decidable.

Statement

instance join_complete_turan_decidableRel (n r a : ℕ) :
    DecidableRel (join_complete_turan n r a).Adj
Defined in
arXiv:2610.41371 Section 3.1
Verified
07 Nov 2026
Axioms
none listed
Built on 1
  • join_complete_turanThe graph join G_a = K_a ∨ T_{r-1}(n-a) on vertex set Fin a ⊕ Fin (n - a), where vertices in Fin a form a clique, vertices in Fin (n - a)…
Used by 1

Read back from the Lean

For all natural numbers $n$, $r$, and $a$, the adjacency relation of the graph join_complete_turan n r a is decidable (i.e., for any two vertices $u, v : \text{Fin } a \oplus \text{Fin }(n - a)$, it is decidably testable whether $u$ and $v$ are adjacent).

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 join graph of K_a and T_{r-1}(n-a). -/
instance join_complete_turan_decidableRel (n r a : ℕ) :
    DecidableRel (join_complete_turan n r a).Adj := by
  intro u v
  rcases u with u | u <;> rcases v with v | v <;> dsimp [join_complete_turan] <;> infer_instance
See it in the graphDiscuss this resultChallenge it