AFTD Auto-Formalizing Theoretical Domains

simple_graph_prism_rung_adj

theoremverified

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.

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

    lines 4–6

    uses SimpleGraph.boxProd_adj

      unfold simple_graph_prism
      rw [SimpleGraph.boxProd_adj]
      left
  2. 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).

    lines 7–8

      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

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