AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_thirteen_eq_iff_permuted_cuts

theoremverified

For every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition has none of the seven cuts (four blocks and three pairs of triples) closed for any color.

Statement

theorem wild_number_complete_thirteen_eq_iff_permuted_cuts
    (c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 9 ↔
      ∃ σ : Equiv.Perm (Fin 13), ∀ (j : Fin 7) (i : Fin 13),
        ¬w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ)
Source
Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10

The proof, explained

The wild number of a proper 13-edge-coloring c of K₁₃ equals 9 if and only if some permutation of the canonical 3+3+3+4 block partition has no color-closed cut among its 7 canonical cuts. In the forward direction, a wild number of 9 yields an optimal 4-block partition with parts of size at least 3, which is necessarily a permutation σ of the canonical 3+3+3+4 partition; the general theory of optimal partitions ensures that no color can leave a union of blocks closed, which rules out any closed cut among the permuted canonical cuts. In the reverse direction, pulling back the canonical partition along σ gives a 4-block partition where every non-trivial cut is a permuted canonical cut or its complement; since none is closed for any color, every color crosses every cut, yielding the upper bound ≤ 13 - 4 = 9, which matches the general lower bound ≥ 9.

  1. The chromatic number of the line graph of K₁₃ is 13, and the equivalence splits into two directions.

    Line 10 enables classical logic. Line 11 uses `complete_graph_odd_line_graph_chromatic_number_eq` to show that the line graph of K₁₃ has chromatic number 13 (since 13 is odd and 13 ≥ 3). Line 12 splits the if-and-only-if statement into the forward implication and the reverse implication.

    lines 10–12

    uses complete_graph_odd_line_graph_chromatic_number_eq

      classical
      have hk := complete_graph_odd_line_graph_chromatic_number_eq 13 (by norm_num) (by decide)
      constructor
  2. Assuming the wild number is 9, there exists an optimal 4-block partition of K₁₃, which yields a candidate vertex permutation σ.

    Line 13 assumes the wild number of c is 9, and line 14 observes that 9 = 4 * ((13 + 1) / 2) / 3. Line 15 applies `wild_number_complete_odd_eq_iff_optimal_partition` to obtain an optimal partition p : Fin 13 → Fin 4 with section r, where each of the four blocks has size at least 3 (`hmin`) and every color class crosses every non-trivial cut between blocks (`hcut`). Because any partition of 13 vertices into 4 parts of size at least 3 must have part sizes 3, 3, 3, 4, line 16 applies `wild_complete_thirteen_partition_template` to obtain a permutation σ of Fin 13 and a permutation β of Fin 4 aligning p with the canonical ownership function `wsc_repair_owner`. Line 17 provides σ as the witness.

    lines 13–17

    uses wild_number_complete_odd_eq_iff_optimal_partition, wild_complete_thirteen_partition_template

      · intro h
        have heq : simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 4*((13+1)/2)/3 := by simpa using h
        obtain ⟨p,r,hr,hmin,hcut⟩ := (wild_number_complete_odd_eq_iff_optimal_partition (by norm_num) (by decide) hk c).1 heq
        obtain ⟨σ,β,hσ⟩ := wild_complete_thirteen_partition_template p hmin
        refine ⟨σ,?_⟩
  3. To show σ works, assume for contradiction that some permuted canonical cut σ(C_j) is closed under color i.

    Line 18 introduces an arbitrary canonical cut index j ∈ {0, …, 6}, a color i, and the hypothesis `hclosed` that the permuted cut σ(C_j) is closed under color i. Lines 19–20 invoke `w279_missing_vertex_equiv` and `wsc_color_used` to find an edge e colored with i (c(e) = i). Lines 21–24 use kernel evaluation (`decide +kernel`) to verify that each canonical cut C_j has size between 1 and 6, and is a union of canonical blocks (`hown`).

    lines 18–24

    uses w279_missing_vertex_equiv, wsc_color_used

        intro j i hclosed
        obtain ⟨m,hm⟩ := w279_missing_vertex_equiv 13 13 (by norm_num) (by decide) hk c
        obtain ⟨e,he⟩ := wsc_color_used (n:=13) (by norm_num) c m hm i
        have hcard : ∀ j : Fin 7, 1 ≤ (wsc_repair_cuts wsc_repair_blocks j).card ∧
            (wsc_repair_cuts wsc_repair_blocks j).card ≤ 6 := by decide +kernel
        have hown : ∀ (j : Fin 7) (u v : Fin 13), u ∈ wsc_repair_cuts wsc_repair_blocks j →
            wsc_repair_owner u = wsc_repair_owner v → v ∈ wsc_repair_cuts wsc_repair_blocks j := by decide +kernel
  4. The permuted cut U = σ(C_j) is a non-empty, proper subset of vertices saturated by the fiber partition p.

    Line 25 sets U = σ(C_j). Lines 26–27 use `Finset.card_image_of_injective` to show |U| = |C_j|. Lines 28–33 establish that U is non-empty and proper (U ≠ univ) since 1 ≤ |U| ≤ 6 < 13. Lines 34–39 show that U is saturated by p: if u ∈ U and p(v) = p(u), then applying β shows that σ⁻¹(v) and σ⁻¹(u) have the same canonical owner; since C_j is a union of canonical blocks, σ⁻¹(v) ∈ C_j and thus v ∈ U.

    lines 25–39

    uses Finset.card_image_of_injective

        let U := (wsc_repair_cuts wsc_repair_blocks j).image σ
        have hcU : U.card = (wsc_repair_cuts wsc_repair_blocks j).card :=
          Finset.card_image_of_injective _ σ.injective
        have hU : U.Nonempty := Finset.card_pos.1 (by have := (hcard j).1; omega)
        have hproper : U ≠ Finset.univ := by
          intro hh
          have hc13 : U.card = 13 := by rw [hh]; simp
          have := (hcard j).2
          omega
        have hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U := by
          intro u hu v hpv
          obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu
          have hvown : wsc_repair_owner (σ.symm v) = wsc_repair_owner x := by
            rw [← hσ (σ.symm v),σ.apply_symm_apply, hpv,hσ x]
          refine Finset.mem_image.2 ⟨σ.symm v, hown j x (σ.symm v) hx hvown.symm, σ.apply_symm_apply v⟩
  5. The closure of U under color i contradicts the optimal partition property that no union of blocks is closed under an edge color.

    Line 40 applies `wild_no_closed_union_of_blocks` to deduce that no non-empty proper union of blocks of the optimal partition p can be closed under the color of any edge e. Line 41 derives a contradiction since c(e) = i and U was assumed closed under color i.

    lines 40–41

    uses wild_no_closed_union_of_blocks

        have hncl := wild_no_closed_union_of_blocks c p hcut e U hU hproper hsat
        exact hncl (by simpa only [he] using hclosed)
  6. Assuming no permuted canonical cut is closed under any color, it suffices to prove the wild number is both ≤ 9 and ≥ 9.

    Line 42 introduces the permutation σ satisfying the hypothesis that no permuted cut σ(C_j) is closed under any color. Line 43 applies `le_antisymm`, reducing the problem to showing wild(c) ≤ 9 and wild(c) ≥ 9.

    lines 42–43

    uses le_antisymm

      · rintro ⟨σ,hσ⟩
        apply le_antisymm
  7. Define a 4-block partition p and representatives r from σ, and classify all non-trivial block subsets.

    Line 44 defines p(v) = wsc_repair_owner(σ⁻¹(v)), and lines 45–46 choose representatives r(t) = σ(3t) for each block t ∈ Fin 4. Lines 47–48 verify that p(r(t)) = t using `Equiv.symm_apply_apply`. Lines 49–51 establish via `decide +kernel` that every non-empty proper subset S ⊂ Fin 4 corresponds under `wsc_repair_owner` to either one of the 7 canonical cuts C_j or its complement (`hshape`).

    lines 44–51

    uses Equiv.symm_apply_apply

        · let p : Fin 13 → Fin 4 := fun v => wsc_repair_owner (σ.symm v)
          let r0 (t : Fin 4) : Fin 13 := ⟨3*t.val,by have := t.isLt; omega⟩
          let r : Fin 4 → Fin 13 := fun t => σ (r0 t)
          have hroot : ∀ t, wsc_repair_owner (r0 t) = t := by decide +kernel
          have hr : ∀ t, p (r t) = t := by intro t; simpa only [p,r,Equiv.symm_apply_apply] using hroot t
          have hshape : ∀ S : Finset (Fin 4), S.Nonempty → S ≠ Finset.univ →
              ∃ j : Fin 7, (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∈ wsc_repair_cuts wsc_repair_blocks j) ∨
                (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∉ wsc_repair_cuts wsc_repair_blocks j) := by decide +kernel
  8. Every edge color crosses every non-trivial cut between blocks of p.

    Lines 52–56 suppose for contradiction that for some edge e and non-empty proper S ⊂ Fin 4, no edge of color c(e) crosses between p⁻¹(S) and p⁻¹(Sᶜ). Line 57 splits on `hshape`. In the first case (lines 58–67), p⁻¹(S) = σ(C_j), so the absence of crossing edges of color c(e) means σ(C_j) is closed under c(e), contradicting the hypothesis hσ. In the second case (lines 68–80), p⁻¹(Sᶜ) = σ(C_j), which similarly implies σ(C_j) is closed under c(e) using edge color symmetry `w279_c_swap`, again contradicting hσ.

    lines 52–80

    uses Equiv.symm_apply_apply, wild_kn_mem, w279_c_swap

          have hcut : ∀ (e : (⊤ : SimpleGraph (Fin 13)).edgeSet) (S : Finset (Fin 4)),
              S.Nonempty → S ≠ Finset.univ →
              ∃ (u v : Fin 13) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by
            intro e S hS hproper
            by_contra! hno
            obtain ⟨j,hj | hj⟩ := hshape S hS hproper
            · apply hσ j (c e)
              intro u hu v huv hc
              obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu
              by_contra hv
              have hxS : p (σ x) ∈ S := by simpa only [p,Equiv.symm_apply_apply] using (hj x).2 hx
              have hvS : p v ∉ S := by
                intro hh
                have hvD := (hj (σ.symm v)).1 hh
                exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩)
              exact hno (σ x) v huv hxS hvS hc
            · apply hσ j (c e)
              intro u hu v huv hc
              obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu
              by_contra hv
              have hxS : p (σ x) ∉ S := by
                intro hh
                have hh' : wsc_repair_owner x ∈ S := by simpa only [p,Equiv.symm_apply_apply] using hh
                exact (hj x).1 hh' hx
              have hvS : p v ∈ S := by
                apply (hj (σ.symm v)).2
                intro hvD
                exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩)
              exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c (Ne.symm huv)).trans hc)
  9. The wild number of c is at most 9.

    Line 81 applies `simple_graph_wild_number_le_of_block_cut_condition` with n = 13 and q = 4, which yields wild(c) ≤ 13 - 4 = 9 because p and r satisfy the cut-crossing condition. Lines 82–83 compute 13 - 4 = 9 with `norm_num` and finish the upper bound.

    lines 81–83

    uses simple_graph_wild_number_le_of_block_cut_condition

          have hu := simple_graph_wild_number_le_of_block_cut_condition (n:=13) (q:=4) (by norm_num) c p r hr hcut
          norm_num at hu
          exact hu
  10. The wild number of c is at least 9, concluding that it equals 9.

    Line 84 applies `wild_number_complete_graph_min_proper_coloring_ge`, which provides the general lower bound 4 * ((13 + 1) / 2) / 3 ≤ wild(c) for any proper 13-coloring of K₁₃. Lines 85–86 evaluate this lower bound to 9 via `norm_num` and close the goal.

    lines 84–86

    uses wild_number_complete_graph_min_proper_coloring_ge

        · have hl := wild_number_complete_graph_min_proper_coloring_ge 13 13 (by norm_num) hk c
          norm_num at hl
          exact hl
complete_graph_odd_line_graph_chromatic_number_eq
For any odd n ≥ 3, the chromatic number of the line graph of the complete graph K_n is equal to n.
wild_number_complete_odd_eq_iff_optimal_partition
For an odd complete graph K_n (n ≥ 3) properly edge-colored with k = χ(L(K_n)) colors, the wild number equals 4⌊(n+1)/2⌋/3 if and only if there exists a vertex partition into ⌊n/3⌋ blocks, each of size at least 3, such that every color class crosses every non-trivial cut between blocks.
wild_complete_thirteen_partition_template
Any partition of a 13-element set into 4 blocks of size at least 3 is isomorphic to the canonical 3+3+3+4 partition via a permutation of the 13 vertices and a permutation of the 4 block labels.
w279_missing_vertex_equiv
In any proper k-edge-coloring of an odd complete graph K_n with k = χ(L(K_n)), each color class misses exactly one vertex, inducing a bijection between the colors and the vertices.
wsc_color_used
In a proper edge-coloring of K_n (n ≥ 3) with a missing-vertex bijection, every color appears on at least one edge.
Finset.card_image_of_injective
An injective function preserves the cardinality of a finite set under image.
wild_no_closed_union_of_blocks
If an edge-coloring satisfies the cut condition for a block partition p, then no non-empty proper union of blocks can be closed under the color of any edge.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
Equiv.symm_apply_apply
Applying an equivalence to the image of an element under its inverse yields the original element: e(e⁻¹(x)) = x.
wild_kn_mem
An unordered pair of distinct vertices in a complete graph forms an edge of the complete graph.
w279_c_swap
The color assigned to an undirected edge {u, v} is symmetric in its endpoints: c({u, v}) = c({v, u}).
simple_graph_wild_number_le_of_block_cut_condition
If a coloring of K_n admits a partition into q blocks with representatives such that every color crosses every non-trivial cut between blocks, then the wild number of the coloring is at most n - q.
wild_number_complete_graph_min_proper_coloring_ge
For any proper edge-coloring of K_n with chromatic number k, the wild number is bounded below by 4⌊(n+1)/2⌋/3.

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

open scoped BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem wild_number_complete_thirteen_eq_iff_permuted_cuts    (c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) :    simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 9 ↔      ∃ σ : Equiv.Perm (Fin 13), ∀ (j : Fin 7) (i : Fin 13),        ¬w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ) := by  classical  have hk := complete_graph_odd_line_graph_chromatic_number_eq 13 (by norm_num) (by decide)  constructor  · intro h    have heq : simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 4*((13+1)/2)/3 := by simpa using h    obtain ⟨p,r,hr,hmin,hcut⟩ := (wild_number_complete_odd_eq_iff_optimal_partition (by norm_num) (by decide) hk c).1 heq    obtain ⟨σ,β,hσ⟩ := wild_complete_thirteen_partition_template p hmin    refine ⟨σ,?_⟩    intro j i hclosed    obtain ⟨m,hm⟩ := w279_missing_vertex_equiv 13 13 (by norm_num) (by decide) hk c    obtain ⟨e,he⟩ := wsc_color_used (n:=13) (by norm_num) c m hm i    have hcard : ∀ j : Fin 7, 1 ≤ (wsc_repair_cuts wsc_repair_blocks j).card ∧        (wsc_repair_cuts wsc_repair_blocks j).card ≤ 6 := by decide +kernel    have hown : ∀ (j : Fin 7) (u v : Fin 13), u ∈ wsc_repair_cuts wsc_repair_blocks j →        wsc_repair_owner u = wsc_repair_owner v → v ∈ wsc_repair_cuts wsc_repair_blocks j := by decide +kernel    let U := (wsc_repair_cuts wsc_repair_blocks j).image σ    have hcU : U.card = (wsc_repair_cuts wsc_repair_blocks j).card :=      Finset.card_image_of_injective _ σ.injective    have hU : U.Nonempty := Finset.card_pos.1 (by have := (hcard j).1; omega)    have hproper : U ≠ Finset.univ := by      intro hh      have hc13 : U.card = 13 := by rw [hh]; simp      have := (hcard j).2      omega    have hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U := by      intro u hu v hpv      obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu      have hvown : wsc_repair_owner (σ.symm v) = wsc_repair_owner x := by        rw [← hσ (σ.symm v),σ.apply_symm_apply, hpv,hσ x]      refine Finset.mem_image.2 ⟨σ.symm v, hown j x (σ.symm v) hx hvown.symm, σ.apply_symm_apply v⟩    have hncl := wild_no_closed_union_of_blocks c p hcut e U hU hproper hsat    exact hncl (by simpa only [he] using hclosed)  · rintro ⟨σ,hσ⟩    apply le_antisymm    · let p : Fin 13 → Fin 4 := fun v => wsc_repair_owner (σ.symm v)      let r0 (t : Fin 4) : Fin 13 := ⟨3*t.val,by have := t.isLt; omega⟩      let r : Fin 4 → Fin 13 := fun t => σ (r0 t)      have hroot : ∀ t, wsc_repair_owner (r0 t) = t := by decide +kernel      have hr : ∀ t, p (r t) = t := by intro t; simpa only [p,r,Equiv.symm_apply_apply] using hroot t      have hshape : ∀ S : Finset (Fin 4), S.Nonempty → S ≠ Finset.univ →          ∃ j : Fin 7, (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∈ wsc_repair_cuts wsc_repair_blocks j) ∨            (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∉ wsc_repair_cuts wsc_repair_blocks j) := by decide +kernel      have hcut : ∀ (e : (⊤ : SimpleGraph (Fin 13)).edgeSet) (S : Finset (Fin 4)),          S.Nonempty → S ≠ Finset.univ →          ∃ (u v : Fin 13) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by        intro e S hS hproper        by_contra! hno        obtain ⟨j,hj | hj⟩ := hshape S hS hproper        · apply hσ j (c e)          intro u hu v huv hc          obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu          by_contra hv          have hxS : p (σ x) ∈ S := by simpa only [p,Equiv.symm_apply_apply] using (hj x).2 hx          have hvS : p v ∉ S := by            intro hh            have hvD := (hj (σ.symm v)).1 hh            exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩)          exact hno (σ x) v huv hxS hvS hc        · apply hσ j (c e)          intro u hu v huv hc          obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu          by_contra hv          have hxS : p (σ x) ∉ S := by            intro hh            have hh' : wsc_repair_owner x ∈ S := by simpa only [p,Equiv.symm_apply_apply] using hh            exact (hj x).1 hh' hx          have hvS : p v ∈ S := by            apply (hj (σ.symm v)).2            intro hvD            exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩)          exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c (Ne.symm huv)).trans hc)      have hu := simple_graph_wild_number_le_of_block_cut_condition (n:=13) (q:=4) (by norm_num) c p r hr hcut      norm_num at hu      exact hu    · have hl := wild_number_complete_graph_min_proper_coloring_ge 13 13 (by norm_num) hk c      norm_num at hl      exact hl
See it in the graphDiscuss this resultChallenge it