AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_proper

theoremverified

Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: proper.

Statement

theorem cyclic_four_block_proper (m : ℕ) (e f : (Fin (2*m+5) × Fin 6))
    (hne : cyclic_four_block_edge m e ≠ cyclic_four_block_edge m f) (ht : cyclic_four_block_touch m e f) :
    cyclic_four_block_col m e ≠ cyclic_four_block_col m f
Source
decomposition of cyclic_four_block_graph_exists_rich_neighbor_five_coloring
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • cyclic_four_block_nextHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the next block index i+1, cyclically mod n=2m+5.
  • cyclic_four_block_srcHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the first endpoint (as a natural number) of the indexed edge (i,j)…
  • cyclic_four_block_dstHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the second endpoint (as a natural number) of the indexed edge (i,j).
  • cyclic_four_block_edgeHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the indexed edge (i,j) of cyclic_four_block_graph m as an unordered…
  • cyclic_four_block_touchHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: two indexed edges share an endpoint (comparison of src/dst values).
  • cyclic_four_block_col_natHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the periodic five-colour assignment to indexed edges, as a natural…
  • cyclic_four_block_colHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the periodic five-colouring of indexed edges, valued in Fin 5.
Used by 1

The proof, explained

The theorem states that the 5-edge-coloring of the cyclic 4-block graph is proper: any two distinct edges that share an endpoint receive different colors. The proof proceeds by contradiction, assuming two distinct touching edges e and f have the same color. It decomposes each edge into a block index and a local index in {0, ..., 5}, exhaustively splits into all 36 combinations of local edge types, and derives a contradiction in every case using linear arithmetic automation (`omega`) and case splitting on block parity and boundary conditions.

  1. Assume for contradiction that the two edges receive the same color, and reduce this to the equality of their numerical color values.

    We assume for contradiction that e and f have the same color under cyclic_four_block_col. Applying Fin.val via congrArg converts this equality of elements in Fin 5 to an equality of the underlying natural numbers, after which the original Fin equality is cleared.

    lines 4–6

    uses congrArg, Fin.val

      intro hc
      have hcv := congrArg Fin.val hc
      clear hc
  2. Decompose each edge into its block index and local edge index, and record the bounds on the block indices.

    We unpack the pair e as (i, j) and f as (k, l), where i and k index the 4-blocks in Fin (2*m+5) and j and l index the six edges within each block in Fin 6. We also extract the bounds i < 2*m+5 and k < 2*m+5 from their types.

    lines 7–11

      rcases e with ⟨i,j⟩
      rcases f with ⟨k,l⟩
      have hi := i.isLt
      have hk := k.isLt
      skip
  3. Split into 36 cases covering all combinations of the local edge indices j and l.

    Because j and l both vary over the finite type Fin 6, we perform an exhaustive case analysis across all 6 × 6 = 36 possible pairs (j, l), creating 36 subgoals.

    line 12

      fin_cases j <;> fin_cases l
  4. Simplify the assumption that e and f are distinct edges into explicit conditions on their endpoints.

    In each of the 36 subgoals, we unfold the definition of cyclic_four_block_edge and simplify the distinctness hypothesis hne using Sym2.eq_iff and ne_eq. This translates the assumption that the edges are distinct into the assertion that their unordered pairs of endpoints do not coincide.

    line 13

    uses ne_eq, cyclic_four_block_edge, Sym2.eq_iff, Prod.mk.injEq, Fin.mk.injEq

      all_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq] at hne
  5. Unfold the definitions of vertex incidence, endpoint coordinates, and the edge coloring.

    We definitionally expand the incidence assumption cyclic_four_block_touch, the vertex coordinate maps cyclic_four_block_src and cyclic_four_block_dst, the coloring maps cyclic_four_block_col and cyclic_four_block_col_nat, and the block successor map cyclic_four_block_next across all hypotheses.

    line 14

    uses cyclic_four_block_touch, cyclic_four_block_src, cyclic_four_block_dst, cyclic_four_block_col, cyclic_four_block_col_nat, cyclic_four_block_next

      all_goals dsimp [cyclic_four_block_touch,cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_col,cyclic_four_block_col_nat,cyclic_four_block_next] at ht hcv hne
  6. Derive a contradiction in every case, showing that adjacent distinct edges cannot have the same color. automation

    In each subgoal, conditional branches arising from cyclic boundary wraparound and parity checks are split using split_ifs. The linear arithmetic solver omega then derives a contradiction among the vertex incidence, distinctness of edges, and equality of color values, discharging every case.

    line 15

      all_goals first | omega | ((try split_ifs at *) <;> (try dsimp at *) <;> omega)
congrArg
Applying a function to both sides of an equality preserves equality: if a = b then f a = f b.
Fin.val
The coercion or projection mapping an element of Fin n to its underlying value in ℕ.
ne_eq
Rewrites an inequality a ≠ b into the logical negation ¬(a = b).
cyclic_four_block_edge
Constructs an undirected edge in the cyclic 4-block graph as an unordered pair (in Sym2) of its two endpoints.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Prod.mk.injEq
Two ordered pairs are equal if and only if their respective components are equal: (a, b) = (c, d) ↔ a = c ∧ b = d.
Fin.mk.injEq
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
cyclic_four_block_touch
The relation stating that two edges share at least one endpoint (source or destination).
cyclic_four_block_src
Computes the source vertex index in ℕ of a given edge.
cyclic_four_block_dst
Computes the destination vertex index in ℕ of a given edge.
cyclic_four_block_col
The 5-coloring function assigning a color in Fin 5 to each edge.
cyclic_four_block_col_nat
The color of an edge represented as a natural number strictly less than 5.
cyclic_four_block_next
The cyclic successor function on block indices, mapping i to (i + 1) mod (2m + 5).

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

Lean’s trace was cut to the first 400 of 982 tactics.

theorem cyclic_four_block_proper (m : ℕ) (e f : (Fin (2*m+5) × Fin 6))    (hne : cyclic_four_block_edge m e ≠ cyclic_four_block_edge m f) (ht : cyclic_four_block_touch m e f) :    cyclic_four_block_col m e ≠ cyclic_four_block_col m f := by  intro hc  have hcv := congrArg Fin.val hc  clear hc  rcases e with ⟨i,j⟩  rcases f with ⟨k,l⟩  have hi := i.isLt  have hk := k.isLt  skip  fin_cases j <;> fin_cases l  all_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq] at hne  all_goals dsimp [cyclic_four_block_touch,cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_col,cyclic_four_block_col_nat,cyclic_four_block_next] at ht hcv hne  all_goals first | omega | ((try split_ifs at *) <;> (try dsimp at *) <;> omega)
See it in the graphDiscuss this resultChallenge it