AFTD Auto-Formalizing Theoretical Domains

simple_graph_categorical_prod

def

The categorical product (tensor product) G × H 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 simple_graph_categorical_prod {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) : SimpleGraph (V × W)
Defined in
arXiv:2610.41977 Sec. 1
Verified
03 Nov 2026
Axioms
none listed
Used by 5

Read back from the Lean

Definition of the categorical (tensor/direct) product of two simple graphs. Given arbitrary types V and W (implicit), and simple graphs G : SimpleGraph V and H : SimpleGraph W (explicit), simple_graph_categorical_prod G H is the simple graph on the product type V × W whose adjacency relation Adj is defined by: two vertices x, y : V × W 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.

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 (tensor) product of two simple graphs. -/
def simple_graph_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.symm := fun x y => by simp [SimpleGraph.adj_comm]
}
See it in the graphDiscuss this resultChallenge it