simple_graph_strong_prod_adj_iff
In 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 (x.2 = y.2 or H.Adj x.2 y.2).
Statement
theorem simple_graph_strong_prod_adj_iff {α β : Type*} (G : SimpleGraph α) (H : SimpleGraph β) (x y : α × β) : (simple_graph_strong_prod G H).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)
- Source
- folklore
- Verified
- 28 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- simple_graph_strong_prodThe 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…
Read back from the Lean
For any types α and β, any simple graph G on α, any simple graph H on β, and any pairs of vertices x, y : α × β, x and y are adjacent in the strong product graph simple_graph_strong_prod G H 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.
The proof, explained
The equivalence holds immediately by definition. In the definition of the strong product graph, adjacency of two pairs x and y is defined to be the condition that x ≠ y, with each coordinate either equal or adjacent in the respective graph. Because both sides of the equivalence are syntactically identical after unfolding the definition, the statement is proved by reflexivity.
The adjacency condition in the strong product is equivalent to the stated conjunction.
The adjacency relation of `simple_graph_strong_prod G H` is defined directly as `x ≠ y ∧ (x.1 = y.1 ∨ G.Adj x.1 y.1) ∧ (x.2 = y.2 ∨ H.Adj x.2 y.2)`. Consequently, the left-hand side and right-hand side are definitionally equal, and the goal is established by reflexivity (`rfl`).
rfl
- This equivalence holds definitionally: the adjacency predicate on the strong product graph is defined to be the exact formula on the right-hand side.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Characterization of adjacency in the strong product of two simple graphs. -/theorem simple_graph_strong_prod_adj_iff {α β : Type*} (G : SimpleGraph α) (H : SimpleGraph β) (x y : α × β) : (simple_graph_strong_prod G H).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) := by rfl