AFTD Auto-Formalizing Theoretical Domains

simple_graph_strong_prod

def

The strong product of two simple graphs G and H: vertices are pairs (u, v) in V(G) × V(H), and two distinct pairs (u, v) and (u', v') are adjacent if (u = u' or G.Adj u u') and (v = v' or H.Adj v v').

Statement

def simple_graph_strong_prod {α β : Type*} (G : SimpleGraph α) (H : SimpleGraph β) :
    SimpleGraph (α × β)
Defined in
G. Sabidussi, The strong product of graphs, Monatshefte für Mathematik 64 (1960), 336–340; W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley, 2000, Section 1.4
Verified
27 Oct 2026
Axioms
none listed
Used by 2

Read back from the Lean

Given types α and β, and simple graphs G : SimpleGraph α and H : SimpleGraph β, simple_graph_strong_prod G H defines the simple graph on the vertex type α × β whose adjacency relation Adj x y holds if and only if x ≠ y, (x.1 = y.1 or G.Adj x.1 y.1), and (x.2 = y.2 or H.Adj x.2 y.2).

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 strong product G ⊠ H of simple graphs G and H. -/
def simple_graph_strong_prod {α β : Type*} (G : SimpleGraph α) (H : SimpleGraph β) :
    SimpleGraph (α × β) where
  Adj x y := x ≠ y ∧ (x.1 = y.1 ∨ G.Adj x.1 y.1) ∧ (x.2 = y.2 ∨ H.Adj x.2 y.2)
  symm := ⟨fun {_ _} h => ⟨h.1.symm,
    h.2.1.elim (fun h1 => Or.inl h1.symm) (fun h1 => Or.inr (G.adj_symm h1)),
    h.2.2.elim (fun h2 => Or.inl h2.symm) (fun h2 => Or.inr (H.adj_symm h2))⟩⟩
  loopless := ⟨fun _ h => h.1 rfl⟩
See it in the graphDiscuss this resultChallenge it