cyclic_four_block_graph_spokes
Each central vertex of cyclic_four_block_graph is adjacent to its three outer vertices.
Statement
theorem cyclic_four_block_graph_spokes (m : ℕ) (i : Fin (2*m+5)) (j : Fin 3) : (cyclic_four_block_graph m).Adj ⟨4*i.val,by omega⟩ ⟨4*i.val+j.val+1,by omega⟩
- Source
- Sanity lemma for cyclic_four_block_graph, the explicit family used for the OP-309 partial case.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cyclic_four_block_graphFor n=2m+5, the graph has vertices b_i,a_i,c_i,d_i and edges b_i-a_i,b_i-c_i,b_i-d_i,a_i-a_next. The c and d strands run forward…
The proof, explained
To show that the central vertex 4i is adjacent to each outer vertex 4i + j + 1 (for j ∈ {0, 1, 2}) in cyclic_four_block_graph m, we unfold the graph definition and apply SimpleGraph.fromEdgeSet_adj to reduce adjacency to edge membership and vertex distinctness. The pair is witnessed by the edge index (i, j), which matches definitionally across all three values of j. Finally, distinctness of the two vertices follows because 4i = 4i + j + 1 is impossible for j ≥ 0 by linear arithmetic.
The vertex indices 4i and 4i + j + 1 are strictly bounded by 4(2m + 5). automation
Linear integer arithmetic (omega) verifies that 4i < 4(2m + 5) and 4i + j + 1 < 4(2m + 5) using the bounds on i < 2m + 5 and j < 3, ensuring that both vertices are valid elements of Fin (4*(2*m+5)).
⟨4*i.val,by omega⟩ ⟨4*i.val+j.val+1,by omega⟩ := by
Adjacency between the central and outer vertices reduces to their unordered pair belonging to the edge set and the vertices being distinct.
Unfolding the definition of cyclic_four_block_graph, the graph is constructed from an explicit set of edges via SimpleGraph.fromEdgeSet. By SimpleGraph.fromEdgeSet_adj, adjacency holds if and only if the undirected pair connecting the two vertices is in that edge set and the two vertices are not equal.
uses
SimpleGraph.fromEdgeSet_adjdsimp only [cyclic_four_block_graph] rw [SimpleGraph.fromEdgeSet_adj]
It suffices to show that the edge indexed by (i, j) produces the desired pair and that the two vertices are distinct.
We provide (i, j.castAdd 3) as the witness showing that the undirected pair is in the range of the graph's edge generator, splitting the goal into checking the edge equality and verifying distinctness.
refine ⟨⟨(i,j.castAdd 3),?_⟩,?_⟩The edge generated by index (i, j) equals the unordered pair {4i, 4i + j + 1}.
Exhausting the three cases for j ∈ Fin 3 (j = 0, 1, 2) via fin_cases, the edge definition simplifies directly to the pair {4i, 4i + j + 1} by reflexivity (rfl) in each case.
· fin_cases j <;> rflThe central vertex 4i and the outer vertex 4i + j + 1 are distinct. automation
Assuming for contradiction that the two vertices are equal, taking their underlying numerical values using congrArg Fin.val yields 4i = 4i + j + 1. Linear integer arithmetic (omega) derives a contradiction since j + 1 > 0.
uses
congrArg,Fin.val· intro h have hv := congrArg Fin.val h dsimp at hv omega
SimpleGraph.fromEdgeSet_adj- In a graph constructed from an edge set, two vertices are adjacent if and only if the undirected pair connecting them is in the edge set and the two vertices are distinct.
congrArg- A function applied to equal arguments yields equal values: if a₁ = a₂ then f a₁ = f a₂.
Fin.val- The projection mapping an element of Fin n to its underlying natural number.
- The theorem statement on line 3 contains inline proofs using omega to verify the bounds required by the Fin type.
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.
theorem cyclic_four_block_graph_spokes (m : ℕ) (i : Fin (2*m+5)) (j : Fin 3) : (cyclic_four_block_graph m).Adj ⟨4*i.val,by omega⟩ ⟨4*i.val+j.val+1,by omega⟩ := by dsimp only [cyclic_four_block_graph] rw [SimpleGraph.fromEdgeSet_adj] refine ⟨⟨(i,j.castAdd 3),?_⟩,?_⟩ · fin_cases j <;> rfl · intro h have hv := congrArg Fin.val h dsimp at hv omega