simple_graph_prism_rung_adj
In the prism graph P₁ □ C_n, every vertex (0, v) in the first copy of the cycle is adjacent to the corresponding vertex (1, v) in the second copy along a rung edge.
Statement
theorem simple_graph_prism_rung_adj (n : ℕ) (v : Fin n) :
(simple_graph_prism n).Adj (0, v) (1, v)- Source
- arXiv:2610.18463 Question 5.4
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_prismThe prism graph P₁ □ C_n on vertex set Fin 2 × Fin n, defined as the Cartesian box product of the 2-vertex complete graph K₂ (the path P₁)…
Read back from the Lean
For every natural number $n$ and every vertex $v : \text{Fin } n$, the vertex $(0, v)$ is adjacent to the vertex $(1, v)$ in simple_graph_prism n.
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 prism graph is defined as the Cartesian box product K₂ □ C_n. Adjacency in a Cartesian product holds when two vertices are adjacent in one factor and identical in the other. For the vertices (0, v) and (1, v), their second coordinates both equal v, and their first coordinates 0 and 1 are distinct and thus adjacent in K₂, establishing that they form a rung edge.
It suffices to show that 0 and 1 are adjacent in the complete graph on two vertices and that their cycle coordinates match.
The prism graph is defined as the Cartesian box product of the complete graph on Fin 2 and the cycle graph of order n. By SimpleGraph.boxProd_adj, adjacency in a box product means the vertices are adjacent in the first factor and equal in the second, or equal in the first and adjacent in the second. Choosing the first case corresponds to moving along a rung edge.
uses
SimpleGraph.boxProd_adjunfold simple_graph_prism rw [SimpleGraph.boxProd_adj] left
Vertices 0 and 1 are adjacent in the complete graph on Fin 2, and v = v. automation
Simplifying the coordinate projections leaves two subgoals: 0 and 1 are adjacent in the complete graph on Fin 2 (which holds because 0 ≠ 1, verified by finite evaluation via decide), and v = v (which holds by definition and reflexivity).
dsimp exact ⟨by decide, rfl⟩
SimpleGraph.boxProd_adj- In the Cartesian box product G □ H, two vertices (u₁, v₁) and (u₂, v₂) are adjacent if and only if either u₁ is adjacent to u₂ in G with v₁ = v₂, or u₁ = u₂ with v₁ adjacent to v₂ in H.
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.
/-- Rung edges connect corresponding vertices in the two cycle copies of a prism graph. -/theorem simple_graph_prism_rung_adj (n : ℕ) (v : Fin n) : (simple_graph_prism n).Adj (0, v) (1, v) := by unfold simple_graph_prism rw [SimpleGraph.boxProd_adj] left dsimp exact ⟨by decide, rfl⟩