AFTD Auto-Formalizing Theoretical Domains

cartesian_product_complete_graphs

def

The Cartesian product of t complete graphs with sizes given by a : Fin t → ℕ, defined as a simple graph on vertex type (i : Fin t) → Fin (a i), where two vertices are adjacent if and only if they differ in exactly one coordinate.

Statement

def cartesian_product_complete_graphs {t : ℕ} (a : Fin t → ℕ) :
    SimpleGraph ((i : Fin t) → Fin (a i))
Defined in
arXiv:2611.03956, Definition 2.6
Verified
04 Nov 2026
Axioms
none listed

Read back from the Lean

Given a natural number $t$ (implicit) and a sequence of natural numbers $a : \text{Fin } t \to \mathbb{N}$, cartesian_product_complete_graphs a is the simple graph with vertex type $\prod_{i : \text{Fin } t} \text{Fin}(a(i))$ (functions $u$ mapping each $i : \text{Fin } t$ to an element of $\text{Fin}(a(i))$), where two vertices $u$ and $v$ are adjacent if and only if there exists a coordinate $j : \text{Fin } t$ such that $u(j) \neq v(j)$ and for all $i : \text{Fin } t$ with $i \neq j$, $u(i) = v(i)$ (i.e., $u$ and $v$ differ at exactly one coordinate).

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

/-- Cartesian product of t complete graphs with vertex set (i : Fin t) → Fin (a i). -/
def cartesian_product_complete_graphs {t : ℕ} (a : Fin t → ℕ) :
    SimpleGraph ((i : Fin t) → Fin (a i)) := by
  refine SimpleGraph.mk (fun u v => ∃ j : Fin t, u j ≠ v j ∧ ∀ i : Fin t, i ≠ j → u i = v i) ?_ ?_
  · exact Std.Symm.mk (by
      intro u v ⟨j, hj, hrest⟩
      exact ⟨j, hj.symm, fun i hi => (hrest i hi).symm⟩)
  · exact Std.Irrefl.mk (by
      intro u ⟨j, hj, _⟩
      exact hj rfl)
See it in the graphDiscuss this resultChallenge it