op_1151_bicirculant_prism_is_hamiltonian
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.
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`.
uses
SimpleGraph.fromRellet 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
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`.
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
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₀.
uses
SimpleGraph.Walk.cons,SimpleGraph.Walk.nillet 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)))))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`.
uses
SimpleGraph.Walk.IsTrail.mk,SimpleGraph.Walk.IsCircuit.mk,SimpleGraph.Walk.IsCycle.mkhave 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)
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.
uses
SimpleGraph.Walk.IsHamiltonian,SimpleGraph.Walk.IsHamiltonianCycle.mkhave h_ham : p.tail.IsHamiltonian := by rw [SimpleGraph.Walk.IsHamiltonian] decide have hp : p.IsHamiltonianCycle := SimpleGraph.Walk.IsHamiltonianCycle.mk h_cycle h_ham
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.
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.
- The adjacency conditions and walk properties (no duplicate edges, no duplicate vertices, and each vertex occurring exactly once in the vertex list) are discharged entirely by computational reflection (`decide`) over the finite graph of order 6.
- In Mathlib, `SimpleGraph.IsHamiltonian` is defined as `Fintype.card V ≠ 1 → ∃ a p, p.IsHamiltonianCycle`, which requires assuming that the vertex set does not have cardinality 1 before providing the cycle witness.
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.
/-- 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⟩