AFTD Auto-Formalizing Theoretical Domains

op_1151_bicirculant_prism_is_hamiltonian

theoremverifiedformalization

The triangular prism bicirculant graph B(3; {1, -1}, {0}, {1, -1}) on vertex set (Fin 2) × (ZMod 3) is Hamiltonian.

Statement

theorem op_1151_bicirculant_prism_is_hamiltonian :
    (SimpleGraph.fromRel fun (u v : Fin 2 × ZMod 3) =>
      (u.1 = 0 ∧ v.1 = 0 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨
      (u.1 = 1 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨
      (u.1 = 0 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({0} : Finset (ZMod 3)))).IsHamiltonian
Formalizes
arXiv:2611.05531 Sec. 1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

The simple graph on vertex set Fin 2 × ZMod 3 generated by SimpleGraph.fromRel from the binary relation R u v holding if and only if: 1. u.1 = 0 ∧ v.1 = 0 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3)), or 2. u.1 = 1 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3)), or 3. u.1 = 0 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({0} : Finset (ZMod 3)) (which forms the triangular prism graph $K_2 \mathbin{\square} C_3$) is Hamiltonian (i.e., satisfies SimpleGraph.IsHamiltonian).

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 proof establishes that the triangular prism bicirculant graph is Hamiltonian by explicitly exhibiting a 6-cycle visiting every vertex. The vertices (0, 0), (0, 1), (0, 2) on the first triangle and (1, 2), (1, 1), (1, 0) on the second triangle are chained together into a closed walk p of length 6. Computational reflection (`decide`) verifies each edge adjacency, confirms that edges and vertices are distinct so that p is a cycle, and verifies that every vertex in the graph is visited exactly once.

  1. Let G denote the triangular prism bicirculant graph, reducing the goal to showing G is Hamiltonian.

    We define G as the simple graph on (Fin 2) × (ZMod 3) whose edges are given by the bicirculant relation (edges within each triangle connecting vertices of difference ±1, and vertical rungs between the two triangles connecting identical ZMod 3 coordinates), and rephrase the goal as `G.IsHamiltonian`.

    lines 7–11

    uses SimpleGraph.fromRel

      let G : SimpleGraph (Fin 2 × ZMod 3) := SimpleGraph.fromRel fun (u v : Fin 2 × ZMod 3) =>
          (u.1 = 0 ∧ v.1 = 0 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨
          (u.1 = 1 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨
          (u.1 = 0 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({0} : Finset (ZMod 3)))
      change G.IsHamiltonian
  2. The sequence of six vertices v₀, ..., v₅ cyclically satisfies the adjacency relation of G.

    We define the candidate cycle vertices v₀ = (0, 0), v₁ = (0, 1), v₂ = (0, 2) on the first triangular face and v₃ = (1, 2), v₄ = (1, 1), v₅ = (1, 0) on the second triangular face. The six adjacency conditions v₀ ~ v₁, v₁ ~ v₂, v₂ ~ v₃, v₃ ~ v₄, v₄ ~ v₅, and v₅ ~ v₀ each reduce to finite modular arithmetic checks in ZMod 3 and are proved by `decide`.

    lines 12–23

      let v0 : Fin 2 × ZMod 3 := (0, 0)
      let v1 : Fin 2 × ZMod 3 := (0, 1)
      let v2 : Fin 2 × ZMod 3 := (0, 2)
      let v3 : Fin 2 × ZMod 3 := (1, 2)
      let v4 : Fin 2 × ZMod 3 := (1, 1)
      let v5 : Fin 2 × ZMod 3 := (1, 0)
      let h01 : G.Adj v0 v1 := by decide
      let h12 : G.Adj v1 v2 := by decide
      let h23 : G.Adj v2 v3 := by decide
      let h34 : G.Adj v3 v4 := by decide
      let h45 : G.Adj v4 v5 := by decide
      let h50 : G.Adj v5 v0 := by decide
  3. Construct the closed walk p from v₀ to v₀ traversing the six edges in order.

    By repeatedly applying `SimpleGraph.Walk.cons` to the six adjacency proofs and terminating with `SimpleGraph.Walk.nil`, we assemble the closed walk p traversing v₀ → v₁ → v₂ → v₃ → v₄ → v₅ → v₀.

    lines 24–26

    uses SimpleGraph.Walk.cons, SimpleGraph.Walk.nil

      let p : G.Walk v0 v0 :=
        SimpleGraph.Walk.cons h01 (SimpleGraph.Walk.cons h12 (SimpleGraph.Walk.cons h23
          (SimpleGraph.Walk.cons h34 (SimpleGraph.Walk.cons h45 (SimpleGraph.Walk.cons h50 SimpleGraph.Walk.nil)))))
  4. The walk p is a simple cycle in G.

    First, p is a trail because its edge list contains no duplicates, verified by `decide` via `SimpleGraph.Walk.IsTrail.mk`. Second, p is a circuit because it is a trail and is non-empty (`p ≠ nil`, verified by `decide`) via `SimpleGraph.Walk.IsCircuit.mk`. Finally, p is a cycle via `SimpleGraph.Walk.IsCycle.mk` because its vertex support excluding the initial vertex (`p.support.tail`) contains no duplicates, as checked by `decide`.

    lines 27–29

    uses SimpleGraph.Walk.IsTrail.mk, SimpleGraph.Walk.IsCircuit.mk, SimpleGraph.Walk.IsCycle.mk

      have h_trail : p.IsTrail := SimpleGraph.Walk.IsTrail.mk (by decide : p.edges.Nodup)
      have h_circuit : p.IsCircuit := SimpleGraph.Walk.IsCircuit.mk h_trail (by decide : p ≠ SimpleGraph.Walk.nil)
      have h_cycle : p.IsCycle := SimpleGraph.Walk.IsCycle.mk h_circuit (by decide : p.support.tail.Nodup)
  5. The walk p is a Hamiltonian cycle in G.

    Rewriting using the definition `SimpleGraph.Walk.IsHamiltonian`, the property `p.tail.IsHamiltonian` means every vertex in (Fin 2) × (ZMod 3) occurs exactly once in the vertex list of `p.tail`. This finite count check is discharged by `decide`. Combining the cycle property and this vertex-exhaustion property via `SimpleGraph.Walk.IsHamiltonianCycle.mk` proves that p is a Hamiltonian cycle.

    lines 30–33

    uses SimpleGraph.Walk.IsHamiltonian, SimpleGraph.Walk.IsHamiltonianCycle.mk

      have h_ham : p.tail.IsHamiltonian := by
        rw [SimpleGraph.Walk.IsHamiltonian]
        decide
      have hp : p.IsHamiltonianCycle := SimpleGraph.Walk.IsHamiltonianCycle.mk h_cycle h_ham
  6. The graph G is Hamiltonian.

    By definition, a graph is Hamiltonian if the vertex cardinality not equaling 1 implies the existence of a Hamiltonian cycle. Assuming the non-triviality hypothesis h on the vertex count, we supply v₀ and the Hamiltonian cycle p to complete the proof.

    lines 34–35

      intro h
      exact ⟨v0, p, hp⟩
SimpleGraph.fromRel
Constructs a simple graph on a vertex set from a binary relation by taking its symmetric, irreflexive closure.
SimpleGraph.Walk.cons
Prepends an edge between adjacent vertices u and v to a walk from v to w, producing a walk from u to w.
SimpleGraph.Walk.nil
The empty walk starting and ending at a given vertex, containing no edges.
SimpleGraph.Walk.IsTrail.mk
Constructs a proof that a walk is a trail from the condition that its list of edges has no duplicate entries.
SimpleGraph.Walk.IsCircuit.mk
Constructs a proof that a closed walk is a circuit from the fact that it is a trail and is not the empty walk.
SimpleGraph.Walk.IsCycle.mk
Constructs a proof that a circuit is a cycle from the condition that its vertex list (excluding the starting vertex) has no duplicate entries.
SimpleGraph.Walk.IsHamiltonian
Predicate asserting that every vertex of the graph occurs with multiplicity 1 in the vertex support list of a walk.
SimpleGraph.Walk.IsHamiltonianCycle.mk
Constructs a proof that a closed walk is a Hamiltonian cycle from the fact that it is a cycle and its tail visits every vertex of the graph exactly once.

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

/-- The triangular prism bicirculant graph B(3; {1, -1}, {0}, {1, -1}) on vertex set (Fin 2) × (ZMod 3) is Hamiltonian. -/theorem op_1151_bicirculant_prism_is_hamiltonian :    (SimpleGraph.fromRel fun (u v : Fin 2 × ZMod 3) =>      (u.1 = 0 ∧ v.1 = 0 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨      (u.1 = 1 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨      (u.1 = 0 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({0} : Finset (ZMod 3)))).IsHamiltonian := by  let G : SimpleGraph (Fin 2 × ZMod 3) := SimpleGraph.fromRel fun (u v : Fin 2 × ZMod 3) =>      (u.1 = 0 ∧ v.1 = 0 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨      (u.1 = 1 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({1, -1} : Finset (ZMod 3))) ∨      (u.1 = 0 ∧ v.1 = 1 ∧ v.2 - u.2 ∈ ({0} : Finset (ZMod 3)))  change G.IsHamiltonian  let v0 : Fin 2 × ZMod 3 := (0, 0)  let v1 : Fin 2 × ZMod 3 := (0, 1)  let v2 : Fin 2 × ZMod 3 := (0, 2)  let v3 : Fin 2 × ZMod 3 := (1, 2)  let v4 : Fin 2 × ZMod 3 := (1, 1)  let v5 : Fin 2 × ZMod 3 := (1, 0)  let h01 : G.Adj v0 v1 := by decide  let h12 : G.Adj v1 v2 := by decide  let h23 : G.Adj v2 v3 := by decide  let h34 : G.Adj v3 v4 := by decide  let h45 : G.Adj v4 v5 := by decide  let h50 : G.Adj v5 v0 := by decide  let p : G.Walk v0 v0 :=    SimpleGraph.Walk.cons h01 (SimpleGraph.Walk.cons h12 (SimpleGraph.Walk.cons h23      (SimpleGraph.Walk.cons h34 (SimpleGraph.Walk.cons h45 (SimpleGraph.Walk.cons h50 SimpleGraph.Walk.nil)))))  have h_trail : p.IsTrail := SimpleGraph.Walk.IsTrail.mk (by decide : p.edges.Nodup)  have h_circuit : p.IsCircuit := SimpleGraph.Walk.IsCircuit.mk h_trail (by decide : p ≠ SimpleGraph.Walk.nil)  have h_cycle : p.IsCycle := SimpleGraph.Walk.IsCycle.mk h_circuit (by decide : p.support.tail.Nodup)  have h_ham : p.tail.IsHamiltonian := by    rw [SimpleGraph.Walk.IsHamiltonian]    decide  have hp : p.IsHamiltonianCycle := SimpleGraph.Walk.IsHamiltonianCycle.mk h_cycle h_ham  intro h  exact ⟨v0, p, hp⟩
See it in the graphDiscuss this resultChallenge it