cyclic_four_block_proper
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
- cyclic_four_block_graph_exists_rich_neighbor_five_coloringFor every m>=0, cyclic_four_block_graph m, on 4(2m+5) vertices, admits a rich-neighbor five-edge-coloring.
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.
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.
uses
congrArg,Fin.valintro hc have hcv := congrArg Fin.val hc clear hc
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.
rcases e with ⟨i,j⟩ rcases f with ⟨k,l⟩ have hi := i.isLt have hk := k.isLt skip
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.
fin_cases j <;> fin_cases l
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.
uses
ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEqall_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq] at hne
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.
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_nextall_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
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.
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).
- The final step relies heavily on automated linear integer arithmetic (`omega`) to discharge all 36 cases and their sub-branches arising from parity and cyclic boundary conditions.
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.
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)