AFTD Auto-Formalizing Theoretical Domains

wild_complete_thirteen_one_swap_repair_obstruction

theoremverified

There exists a minimum proper 13-coloring of K_13, normalized so that color i misses vertex i, with this property. The fixed partition {0,1,2}, {3,4,5}, {6,7,8}, {9,10,11,12} has exactly one closed color cut among the seven cuts up to complements: its first triple, for color 0. Every single swap of vertices from different blocks leaves a closed color cut. Swapping vertices 0 and 3 and then vertices 0 and 6 produces a partition with no closed color cut. The seven cuts are the four individual blocks and the three unions of two of the triple blocks.

Statement

theorem wild_complete_thirteen_one_swap_repair_obstruction :
    (⊤ : SimpleGraph (Fin 13)).lineGraph.chromaticNumber = 13 ∧
    ∃ c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13),
      (∀ i v : Fin 13, (∀ w (hvw : v ≠ w), c ⟨s(v,w), wild_kn_mem hvw⟩ ≠ i) ↔ v = i) ∧
      (∀ (j : Fin 7) (i : Fin 13), w279_closed c i (wsc_repair_cuts wsc_repair_blocks j) ↔ j = 0 ∧ i = 0) ∧
      (∀ u v : Fin 13, wsc_repair_owner u ≠ wsc_repair_owner v →
        ∃ (j : Fin 7) (i : Fin 13), w279_closed c i
          (wsc_repair_cuts (wsc_repair_swap wsc_repair_blocks u v) j)) ∧
      (∀ (j : Fin 7) (i : Fin 13), ¬w279_closed c i
        (wsc_repair_cuts (wsc_repair_swap (wsc_repair_swap wsc_repair_blocks 0 3) 0 6) j))
Source
Obstruction to a proposed finite-range repair step for OP-306. Experiment 7988 constructs the symmetric idempotent color table; the Lean proof independently checks its rows, the unique bad cut, all swaps, and the displayed two-swap repair using kernel reduction. This is a failed proof-route certificate; the original conjecture remains open.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 5

The proof, explained

The theorem constructs an explicit minimum proper 13-edge-coloring of $K_{13}$, normalized so that color $i$ misses vertex $i$, which demonstrates a one-swap repair obstruction on the partition $\{0,1,2\}, \{3,4,5\}, \{6,7,8\}, \{9,10,11,12\}$. The coloring is defined from a symmetric $13 \times 13$ Latin square table with diagonal entries $v$. The chromatic index $\chi'(K_{13}) = 13$ is given by the general theorem for complete graphs of odd order, while all combinatorial assertions—that the initial partition has a unique closed cut (cut 0 for color 0), that every cross-block single swap leaves at least one closed cut, and that the double swap $(0\ 3)$ followed by $(0\ 6)$ repairs all seven cuts—are verified by finite kernel computation (`decide +kernel`).

  1. The block index mapping is well-defined. automation

    The block owner of a vertex $v \in \{0, \dots, 12\}$ is defined as $\min(\lfloor v/3 \rfloor, 3)$. The linear arithmetic tactic `omega` proves that this value is strictly less than 4, ensuring it is a valid index in `Fin 4`.

    line 25

    def wsc_repair_owner (v : Fin 13) : Fin 4 := ⟨min (v.val/3) 3, by omega⟩
  2. The condition that a subset $U$ is closed under color $i$ in `wsc_repair_table` is decidable.

    Unfolding the definition of `wsc_repair_closed` expresses it as bounded universal quantifications over the finite set $U$ and finite type `Fin 13`, allowing typeclass inference to synthesize a `Decidable` instance.

    lines 33–34

    instance wsc_repair_closed_decidable (i : Fin 13) (U : Finset (Fin 13)) :
        Decidable (wsc_repair_closed i U) := by unfold wsc_repair_closed; infer_instance
  3. The matrix `wsc_repair_table` is symmetric, has diagonal entries $T(v, v) = v$, and has distinct entries in each row. automation

    Direct computation by the Lean kernel (`decide +kernel`) verifies that the $13 \times 13$ table has $v$ along the diagonal, satisfies $T(u, v) = T(v, u)$, and satisfies $T(v, u) = T(v, w) \implies u = w$.

    lines 36–40

    uses wsc_repair_table_valid

    lemma wsc_repair_table_valid :
        (∀ v : Fin 13, wsc_repair_table v v = v) ∧
        (∀ u v : Fin 13, wsc_repair_table u v = wsc_repair_table v u) ∧
        (∀ v u w : Fin 13, wsc_repair_table v u = wsc_repair_table v w → u = w) := by
      decide +kernel
  4. For each vertex $v$, color $i$ does not appear on any off-diagonal entry in row $v$ if and only if $v = i$. automation

    Direct computation by the Lean kernel (`decide +kernel`) checks for all $v, i \in \{0, \dots, 12\}$ that the off-diagonal entries in row $v$ miss color $i$ exactly when $v = i$.

    lines 42–44

    uses wsc_repair_table_missing

    lemma wsc_repair_table_missing :
        ∀ i v : Fin 13, (∀ w : Fin 13, v ≠ w → wsc_repair_table v w ≠ i) ↔ v = i := by
      decide +kernel
  5. In the initial partition, exactly one cut is closed: the first block $\{0,1,2\}$ for color 0. automation

    Direct computation by the Lean kernel (`decide +kernel`) evaluates all $7 \times 13 = 91$ combinations of candidate cuts and colors, confirming that cut $j$ is closed under color $i$ if and only if $j = 0$ and $i = 0$.

    lines 46–48

    uses wsc_repair_unique_bad_cut

    lemma wsc_repair_unique_bad_cut :
        ∀ (j : Fin 7) (i : Fin 13), wsc_repair_closed i (wsc_repair_cuts wsc_repair_blocks j) ↔ j = 0 ∧ i = 0 := by
      decide +kernel
  6. Every single swap of two vertices from different blocks leaves at least one closed cut. automation

    Direct computation by the Lean kernel (`decide +kernel`) checks every pair of vertices $(u, v)$ with different block owners, confirming that in the swapped partition there is always some cut $j \in \{0, \dots, 6\}$ and color $i$ such that cut $j$ is closed under color $i$.

    lines 50–54

    uses wsc_repair_all_swaps_bad

    lemma wsc_repair_all_swaps_bad :
        ∀ u v : Fin 13, wsc_repair_owner u ≠ wsc_repair_owner v →
          ∃ (j : Fin 7) (i : Fin 13),
            wsc_repair_closed i (wsc_repair_cuts (wsc_repair_swap wsc_repair_blocks u v) j) := by
      decide +kernel
  7. Swapping vertices 0 and 3, then vertices 0 and 6, leaves no closed cuts for any color. automation

    Direct computation by the Lean kernel (`decide +kernel`) tests the partition obtained after the two transpositions $(0\ 3)$ and $(0\ 6)$, verifying that none of the seven cuts is closed under any color.

    lines 56–59

    uses wsc_repair_two_swaps_good

    lemma wsc_repair_two_swaps_good :
        ∀ (j : Fin 7) (i : Fin 13), ¬wsc_repair_closed i
          (wsc_repair_cuts (wsc_repair_swap (wsc_repair_swap wsc_repair_blocks 0 3) 0 6) j) := by
      decide +kernel
  8. The matrix `wsc_repair_table` induces a proper 13-coloring of the line graph of $K_{13}$.

    Since `wsc_repair_table` is symmetric (`wsc_repair_table_valid`), it lifts via `Sym2.lift` to assign a color to every unordered pair of vertices. To see the coloring is proper, suppose two distinct incident edges $e_1, e_2$ have the same color. By `SimpleGraph.lineGraph_adj_iff_exists` and `Sym2.mem_iff_exists.mp`, they share a vertex $v$ and can be written as $e_1 = \{v, a\}$ and $e_2 = \{v, b\}$. Their colors being equal means $T(v, a) = T(v, b)$ by `Sym2.lift_mk`. By row injectivity (`wsc_repair_table_valid`), $a = b$, which via `Subtype.ext` implies $e_1 = e_2$, a contradiction.

    lines 61–75

    uses wsc_repair_table_valid, SimpleGraph.lineGraph_adj_iff_exists, Sym2.mem_iff_exists.mp, Sym2.lift_mk, Subtype.ext

    noncomputable def wsc_repair_coloring :
        (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13) := by
      let col : Sym2 (Fin 13) → Fin 13 := Sym2.lift ⟨wsc_repair_table, wsc_repair_table_valid.2.1⟩
      refine SimpleGraph.Coloring.mk (fun e => col e.val) ?_
      intro e₁ e₂ h hc
      rw [SimpleGraph.lineGraph_adj_iff_exists] at h
      obtain ⟨hne, v, h1, h2⟩ := h
      obtain ⟨a, ha⟩ := Sym2.mem_iff_exists.mp h1
      obtain ⟨b, hb⟩ := Sym2.mem_iff_exists.mp h2
      have ht : wsc_repair_table v a = wsc_repair_table v b := by
        simpa only [col, ha, hb, Sym2.lift_mk] using hc
      have hab := wsc_repair_table_valid.2.2 v a b ht
      apply hne
      apply Subtype.ext
      rw [ha,hb,hab]
  9. A vertex set is closed in the line graph coloring if and only if it is closed in the table.

    By `wsc_repair_coloring_pair`, the edge coloring on distinct vertices agrees with the matrix entries. In the forward direction, if $v = w$, then $w = v \in U$ holds trivially. In the backward direction, the non-diagonal condition translates directly between the graph coloring and the table.

    lines 80–88

    uses wsc_repair_coloring_pair

    lemma wsc_repair_closed_iff (i : Fin 13) (U : Finset (Fin 13)) :
        w279_closed wsc_repair_coloring i U ↔ wsc_repair_closed i U := by
      constructor
      · intro h v hv w hc
        by_cases he : v = w
        · simpa only [← he] using hv
        · exact h v hv w he ((wsc_repair_coloring_pair v w he).trans hc)
      · intro h v hv w hvw hc
        exact h v hv w ((wsc_repair_coloring_pair v w hvw).symm.trans hc)
  10. The line graph of $K_{13}$ has chromatic number 13, and `wsc_repair_coloring` is a candidate 13-coloring.

    The theorem `complete_graph_odd_line_graph_chromatic_number_eq` with $n = 13$, using `norm_num` to check $3 \le 13$ and `decide` to check that 13 is odd, shows that $\chi'(K_{13}) = 13$. The proof refines the existential claim by providing `wsc_repair_coloring` as the coloring witness.

    lines 90–100

    uses complete_graph_odd_line_graph_chromatic_number_eq

    theorem wild_complete_thirteen_one_swap_repair_obstruction :
        (⊤ : SimpleGraph (Fin 13)).lineGraph.chromaticNumber = 13 ∧
        ∃ c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13),
          (∀ i v : Fin 13, (∀ w (hvw : v ≠ w), c ⟨s(v,w), wild_kn_mem hvw⟩ ≠ i) ↔ v = i) ∧
          (∀ (j : Fin 7) (i : Fin 13), w279_closed c i (wsc_repair_cuts wsc_repair_blocks j) ↔ j = 0 ∧ i = 0) ∧
          (∀ u v : Fin 13, wsc_repair_owner u ≠ wsc_repair_owner v →
            ∃ (j : Fin 7) (i : Fin 13), w279_closed c i
              (wsc_repair_cuts (wsc_repair_swap wsc_repair_blocks u v) j)) ∧
          (∀ (j : Fin 7) (i : Fin 13), ¬w279_closed c i
            (wsc_repair_cuts (wsc_repair_swap (wsc_repair_swap wsc_repair_blocks 0 3) 0 6) j)) := by
      refine ⟨complete_graph_odd_line_graph_chromatic_number_eq 13 (by norm_num) (by decide), wsc_repair_coloring, ?_, ?_, ?_, ?_⟩
  11. In `wsc_repair_coloring`, color $i$ misses vertex $v$ if and only if $v = i$.

    Rewriting with `wsc_repair_table_missing` reduces the claim to the corresponding property of `wsc_repair_table`. Applying `wsc_repair_coloring_pair` converts between edge colors and table entries for distinct vertices in both directions.

    lines 101–109

    uses wsc_repair_table_missing, wsc_repair_coloring_pair

      · intro i v
        rw [← wsc_repair_table_missing i v]
        constructor
        · intro h w hvw
          rw [← wsc_repair_coloring_pair v w hvw]
          exact h w hvw
        · intro h w hvw
          rw [wsc_repair_coloring_pair v w hvw]
          exact h w hvw
  12. In the unswapped partition, cut $j$ is closed under color $i$ if and only if $j = 0$ and $i = 0$.

    Rewriting with `wsc_repair_closed_iff` translates the graph closure predicate `w279_closed` to the table predicate `wsc_repair_closed`, after which `wsc_repair_unique_bad_cut` closes the goal.

    lines 110–112

    uses wsc_repair_closed_iff, wsc_repair_unique_bad_cut

      · intro j i
        rw [wsc_repair_closed_iff]
        exact wsc_repair_unique_bad_cut j i
  13. Every cross-block swap leaves at least one closed cut in `wsc_repair_coloring`.

    For any vertices $u, v$ in different blocks, `wsc_repair_all_swaps_bad` provides a cut index $j$ and color $i$ that remains closed in the table. Applying `wsc_repair_closed_iff` transfers this closed cut to the graph coloring.

    lines 113–115

    uses wsc_repair_all_swaps_bad, wsc_repair_closed_iff

      · intro u v huv
        obtain ⟨j,i,hi⟩ := wsc_repair_all_swaps_bad u v huv
        exact ⟨j,i,(wsc_repair_closed_iff i _).2 hi⟩
  14. The two-swap partition has no closed cuts under any color in `wsc_repair_coloring`.

    Rewriting with `wsc_repair_closed_iff` translates the goal to `wsc_repair_closed`, which is discharged by `wsc_repair_two_swaps_good`.

    lines 116–118

    uses wsc_repair_closed_iff, wsc_repair_two_swaps_good

      · intro j i
        rw [wsc_repair_closed_iff]
        exact wsc_repair_two_swaps_good j i
complete_graph_odd_line_graph_chromatic_number_eq
For any odd integer $n \ge 3$, the chromatic number of the line graph of $K_n$ is $n$.
wsc_repair_table_missing
In `wsc_repair_table`, color $i$ does not appear in row $v$ away from the diagonal if and only if $v = i$.
wsc_repair_coloring_pair
The color assigned to the edge between distinct vertices $u$ and $v$ by `wsc_repair_coloring` is the entry `wsc_repair_table u v`.
wsc_repair_closed_iff
A vertex set $U$ is closed under color $i$ with respect to the line graph edge coloring if and only if it is closed under color $i$ with respect to `wsc_repair_table`.
wsc_repair_unique_bad_cut
Among the seven candidate cuts and thirteen colors, cut $j$ is closed under color $i$ in `wsc_repair_table` if and only if $j = 0$ (the block $\{0,1,2\}$) and $i = 0$.
wsc_repair_all_swaps_bad
Every single swap of two vertices belonging to different blocks produces a partition with at least one cut closed under some color in `wsc_repair_table`.
wsc_repair_two_swaps_good
After swapping vertices 0 and 3, then vertices 0 and 6, none of the seven candidate cuts is closed under any color in `wsc_repair_table`.
wsc_repair_table_valid
The matrix `wsc_repair_table` has diagonal entry $v$, is symmetric, and has no repeated entries in any row.
SimpleGraph.lineGraph_adj_iff_exists
Two distinct edges of a graph are adjacent in its line graph if and only if they share a common vertex.
Sym2.mem_iff_exists.mp
A vertex $v$ belongs to an unordered pair $e$ if and only if $e = \{v, y\}$ for some vertex $y$.
Sym2.lift_mk
Evaluating the lift of a symmetric bivariate function on the unordered pair $\{a, b\}$ yields the function value $f(a, b)$.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.

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

set_option maxHeartbeats 1000000set_option maxRecDepth 100000def wsc_repair_table : Fin 13 → Fin 13 → Fin 13 := ![  ![0, 8, 12, 4, 5, 1, 10, 2, 9, 6, 11, 3, 7],  ![8, 1, 0, 7, 11, 3, 9, 6, 10, 5, 2, 12, 4],  ![12, 0, 2, 5, 1, 10, 8, 11, 7, 4, 6, 9, 3],  ![4, 7, 5, 3, 10, 11, 2, 9, 6, 12, 8, 1, 0],  ![5, 11, 1, 10, 4, 9, 3, 0, 2, 7, 12, 6, 8],  ![1, 3, 10, 11, 9, 5, 7, 4, 12, 2, 0, 8, 6],  ![10, 9, 8, 2, 3, 7, 6, 12, 11, 1, 4, 0, 5],  ![2, 6, 11, 9, 0, 4, 12, 7, 3, 8, 1, 5, 10],  ![9, 10, 7, 6, 2, 12, 11, 3, 8, 0, 5, 4, 1],  ![6, 5, 4, 12, 7, 2, 1, 8, 0, 9, 3, 10, 11],  ![11, 2, 6, 8, 12, 0, 4, 1, 5, 3, 10, 7, 9],  ![3, 12, 9, 1, 6, 8, 0, 5, 4, 10, 7, 11, 2],  ![7, 4, 3, 0, 8, 6, 5, 10, 1, 11, 9, 2, 12]]def wsc_repair_blocks : Fin 4 → Finset (Fin 13) := ![{0,1,2},{3,4,5},{6,7,8},{9,10,11,12}]def wsc_repair_cuts (B : Fin 4 → Finset (Fin 13)) : Fin 7 → Finset (Fin 13) :=  ![B 0, B 1, B 2, B 3, B 0 ∪ B 1, B 0 ∪ B 2, B 1 ∪ B 2]def wsc_repair_owner (v : Fin 13) : Fin 4 := ⟨min (v.val/3) 3, by omega⟩def wsc_repair_swap (B : Fin 4 → Finset (Fin 13)) (u v : Fin 13) : Fin 4 → Finset (Fin 13) :=  fun t => (B t).image (Equiv.swap u v)def wsc_repair_closed (i : Fin 13) (U : Finset (Fin 13)) : Prop :=  ∀ v ∈ U, ∀ w : Fin 13, wsc_repair_table v w = i → w ∈ Uinstance wsc_repair_closed_decidable (i : Fin 13) (U : Finset (Fin 13)) :    Decidable (wsc_repair_closed i U) := by unfold wsc_repair_closed; infer_instancelemma wsc_repair_table_valid :    (∀ v : Fin 13, wsc_repair_table v v = v) ∧    (∀ u v : Fin 13, wsc_repair_table u v = wsc_repair_table v u) ∧    (∀ v u w : Fin 13, wsc_repair_table v u = wsc_repair_table v w → u = w) := by  decide +kernellemma wsc_repair_table_missing :    ∀ i v : Fin 13, (∀ w : Fin 13, v ≠ w → wsc_repair_table v w ≠ i) ↔ v = i := by  decide +kernellemma wsc_repair_unique_bad_cut :    ∀ (j : Fin 7) (i : Fin 13), wsc_repair_closed i (wsc_repair_cuts wsc_repair_blocks j) ↔ j = 0 ∧ i = 0 := by  decide +kernellemma wsc_repair_all_swaps_bad :    ∀ u v : Fin 13, wsc_repair_owner u ≠ wsc_repair_owner v →      ∃ (j : Fin 7) (i : Fin 13),        wsc_repair_closed i (wsc_repair_cuts (wsc_repair_swap wsc_repair_blocks u v) j) := by  decide +kernellemma wsc_repair_two_swaps_good :    ∀ (j : Fin 7) (i : Fin 13), ¬wsc_repair_closed i      (wsc_repair_cuts (wsc_repair_swap (wsc_repair_swap wsc_repair_blocks 0 3) 0 6) j) := by  decide +kernelnoncomputable def wsc_repair_coloring :    (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13) := by  let col : Sym2 (Fin 13) → Fin 13 := Sym2.lift ⟨wsc_repair_table, wsc_repair_table_valid.2.1⟩  refine SimpleGraph.Coloring.mk (fun e => col e.val) ?_  intro e₁ e₂ h hc  rw [SimpleGraph.lineGraph_adj_iff_exists] at h  obtain ⟨hne, v, h1, h2⟩ := h  obtain ⟨a, ha⟩ := Sym2.mem_iff_exists.mp h1  obtain ⟨b, hb⟩ := Sym2.mem_iff_exists.mp h2  have ht : wsc_repair_table v a = wsc_repair_table v b := by    simpa only [col, ha, hb, Sym2.lift_mk] using hc  have hab := wsc_repair_table_valid.2.2 v a b ht  apply hne  apply Subtype.ext  rw [ha,hb,hab]lemma wsc_repair_coloring_pair (u v : Fin 13) (h : u ≠ v) :    wsc_repair_coloring ⟨s(u,v), wild_kn_mem h⟩ = wsc_repair_table u v := rfllemma wsc_repair_closed_iff (i : Fin 13) (U : Finset (Fin 13)) :    w279_closed wsc_repair_coloring i U ↔ wsc_repair_closed i U := by  constructor  · intro h v hv w hc    by_cases he : v = w    · simpa only [← he] using hv    · exact h v hv w he ((wsc_repair_coloring_pair v w he).trans hc)  · intro h v hv w hvw hc    exact h v hv w ((wsc_repair_coloring_pair v w hvw).symm.trans hc)theorem wild_complete_thirteen_one_swap_repair_obstruction :    (⊤ : SimpleGraph (Fin 13)).lineGraph.chromaticNumber = 13 ∧    ∃ c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13),      (∀ i v : Fin 13, (∀ w (hvw : v ≠ w), c ⟨s(v,w), wild_kn_mem hvw⟩ ≠ i) ↔ v = i) ∧      (∀ (j : Fin 7) (i : Fin 13), w279_closed c i (wsc_repair_cuts wsc_repair_blocks j) ↔ j = 0 ∧ i = 0) ∧      (∀ u v : Fin 13, wsc_repair_owner u ≠ wsc_repair_owner v →        ∃ (j : Fin 7) (i : Fin 13), w279_closed c i          (wsc_repair_cuts (wsc_repair_swap wsc_repair_blocks u v) j)) ∧      (∀ (j : Fin 7) (i : Fin 13), ¬w279_closed c i        (wsc_repair_cuts (wsc_repair_swap (wsc_repair_swap wsc_repair_blocks 0 3) 0 6) j)) := by  refine ⟨complete_graph_odd_line_graph_chromatic_number_eq 13 (by norm_num) (by decide), wsc_repair_coloring, ?_, ?_, ?_, ?_⟩  · intro i v    rw [← wsc_repair_table_missing i v]    constructor    · intro h w hvw      rw [← wsc_repair_coloring_pair v w hvw]      exact h w hvw    · intro h w hvw      rw [wsc_repair_coloring_pair v w hvw]      exact h w hvw  · intro j i    rw [wsc_repair_closed_iff]    exact wsc_repair_unique_bad_cut j i  · intro u v huv    obtain ⟨j,i,hi⟩ := wsc_repair_all_swaps_bad u v huv    exact ⟨j,i,(wsc_repair_closed_iff i _).2 hi⟩  · intro j i    rw [wsc_repair_closed_iff]    exact wsc_repair_two_swaps_good j i
See it in the graphDiscuss this resultChallenge it