AFTD Auto-Formalizing Theoretical Domains

simple_graph_strong_prod_adj_iff

theoremverified

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.

  1. 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`).

    line 5

      rfl

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

/-- 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
See it in the graphDiscuss this resultChallenge it