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
- cycle_strong_product_not_has_equivalence_cover_threeFor every m ≥ 6 and n ≥ 5, the strong product of cycles C_m and C_n (simple_graph_strong_prod of simple_graph_cycle_power m 1 and…
- simple_graph_strong_prod_adj_iffIn the strong product of simple graphs G and H, two pairs x and y are adjacent if and only if x ≠ y, (x.1 = y.1 or G.Adj x.1 y.1), and…
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⟩