AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_graph_spokes

theoremverified

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.

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

    line 3

          ⟨4*i.val,by omega⟩ ⟨4*i.val+j.val+1,by omega⟩ := by
  2. 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.

    lines 4–5

    uses SimpleGraph.fromEdgeSet_adj

      dsimp only [cyclic_four_block_graph]
      rw [SimpleGraph.fromEdgeSet_adj]
  3. 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.

    line 6

      refine ⟨⟨(i,j.castAdd 3),?_⟩,?_⟩
  4. 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.

    line 7

      · fin_cases j <;> rfl
  5. The 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.

    lines 8–11

    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.

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

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