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⟩ }