AFTD Auto-Formalizing Theoretical Domains

categorical_prod

def

The categorical product of two simple graphs G and H has vertex set V(G) × V(H), with an edge between (u₁, v₁) and (u₂, v₂) if and only if u₁ is adjacent to u₂ in G and v₁ is adjacent to v₂ in H.

Statement

def categorical_prod {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) : SimpleGraph (V × W)
Defined in
arXiv:2610.41977, Sec. 1
Verified
02 Nov 2026
Axioms
none listed

Read back from the Lean

Given types V and W, and simple graphs G on V and H on W, categorical_prod G H is the simple graph on the product type V × W where two vertices x and y are adjacent if and only if x.1 is adjacent to y.1 in G and x.2 is adjacent to y.2 in H (with symmetry given by the symmetry of adjacency in G and H, and irreflexivity given by the irreflexivity of G).

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

/-- The categorical product (tensor product) of simple graphs: (u₁, v₁) is adjacent to (u₂, v₂) if and only if u₁ ~ u₂ in G and v₁ ~ v₂ in H. -/
def categorical_prod {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) : SimpleGraph (V × W) := {
  Adj := fun x y => G.Adj x.1 y.1 ∧ H.Adj x.2 y.2
  symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.symm⟩⟩
  loopless := ⟨fun _ h => G.loopless.irrefl _ h.1⟩
}
See it in the graphDiscuss this resultChallenge it