AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_graph_upper_sub_four_add_parity

theoremverifiedoriginal

For every integer n>=13, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge coloring c of K_n with color set Fin k, the wild number is at most (n-4)+(n mod 2). This is n-3 for odd n>=13 and n-4 for even n>=14.

Statement

theorem wild_number_complete_graph_upper_sub_four_add_parity (n k : ℕ) (hn : 13 ≤ n)
    (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c ≤ n-4+n%2
Related work
arXiv:2610.22142, Section 3.3.4, Theorem 3.6 and its even-order corollary give n-2 for odd n and n-3 for even n. This strengthens each weak upper bound by one on n>=13. The proof randomly permutes two triples and the remaining n-6 vertices; closure of the remaining block is equivalent to closure of the union of the triples. No equality with the conjectured lower bound is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 3

Read back from the Lean

For any natural numbers $n$ and $k$, assuming: 1. $13 \le n$, 2. $k$ is the chromatic number of the line graph of the complete graph $K_n$ on vertex set $\mathrm{Fin}(n)$ (i.e., $k$ is the chromatic index $\chi'(K_n)$), and 3. $c$ is a proper coloring of the line graph of $K_n$ with colors in $\mathrm{Fin}(k)$ (i.e., a proper edge-coloring of $K_n$ using $k$ colors), the "wild number" of $K_n$ with respect to $c$ (the minimum size of an edge set $W \subseteq E(K_n)$ such that for every edge $e$, adding $W$ to the edges of color $c(e)$ produces a connected spanning subgraph) is at most $(n - 4) + (n \bmod 2)$ (which equals $n - 4$ if $n$ is even, and $n - 3$ if $n$ is odd).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem bounds the wild number of the complete graph K_n under an optimal edge coloring by (n - 4) + (n mod 2) for all n ≥ 13. For odd n, the vertices are partitioned into three blocks (two of size 3 and one of size n - 6) using the probabilistic method: counting arguments and polynomial bounds ensure there exists a permutation whose block images are never closed under any color matching, so every color crosses every non-trivial cut, yielding wild number ≤ n - 3. For even n, the coloring is restricted to the odd subgraph K_{n-1}, where the 3-partition is constructed and then lifted to K_n to achieve the bound ≤ n - 4.

  1. The number of permutations of Fin n extending a given injective partial map f on D is at most (n - |D|)!.

    We apply the switching bound lemma permutation_partial_assignment_card_bound_of_switching to the universe of permutations, which bounds n^{\underline{|D|}} times the fiber by n!. Dividing both sides by n^{\underline{|D|}} via Nat.le_of_mul_le_mul_left yields the bound (n - |D|)!.

    lines 8–20

    uses permutation_partial_assignment_card_bound_of_switching, Nat.factorial_mul_descFactorial, Nat.descFactorial_pos, Nat.le_of_mul_le_mul_left, Nat.mul_comm, Finset.card_le_univ

      classical
      have hi := permutation_partial_assignment_card_bound_of_switching D f hf
        (Finset.univ : Finset (Equiv.Perm (Fin n))) (by intro a ha σ hσ hσa y; exact Finset.mem_univ _)
      simp only [Fintype.card_fin, Finset.card_univ, Fintype.card_perm] at hi
      have hd : D.card ≤ n := by simpa using Finset.card_le_univ D
      have he := Nat.factorial_mul_descFactorial hd
      have hp : 0 < (n : ℕ).descFactorial D.card := Nat.descFactorial_pos.2 hd
      apply Nat.le_of_mul_le_mul_left (c := (n : ℕ).descFactorial D.card) (hc := hp)
      convert hi.trans_eq (he.symm.trans (Nat.mul_comm _ _)) using 1
      congr 1
      apply congrArg Finset.card
      ext σ
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
  2. Every permutation σ whose image σ(D) is closed under color i projects to an injection φ(σ) agreeing with σ on D and the identity elsewhere.

    We define φ(σ)(x) to be σ(x) if x ∈ D and x otherwise. Since σ is injective, φ(σ) is injective on D and satisfies φ(σ)(D) = σ(D), so φ(σ)(D) is also closed under color i.

    lines 30–52

    uses if_neg, if_pos, Finset.image_congr

      classical
      let A : Finset (Equiv.Perm (Fin n)) := Finset.univ.filter fun σ => w279_closed c i (D.image σ)
      let F : Finset (Fin n → Fin n) := Finset.univ.filter fun f =>
        (∀ x ∉ D, f x = x) ∧ Set.InjOn f (↑D : Set (Fin n)) ∧ w279_closed c i (D.image f)
      let φ : Equiv.Perm (Fin n) → Fin n → Fin n := fun σ x => if x ∈ D then σ x else x
      have hmaps : ∀ σ ∈ A, φ σ ∈ F := by
        intro σ hσ
        simp only [F, Finset.mem_filter, Finset.mem_univ, true_and]
        refine ⟨?_, ?_, ?_⟩
        · intro x hx; simp only [φ, if_neg hx]
        · intro x hx y hy he
          change x ∈ D at hx
          change y ∈ D at hy
          dsimp only [φ] at he
          rw [if_pos hx, if_pos hy] at he
          exact σ.injective he
        · have he : D.image (φ σ) = D.image σ := by
            apply Finset.image_congr
            intro x hx
            change x ∈ D at hx
            simp only [φ, if_pos hx]
          rw [he]
          exact (Finset.mem_filter.1 hσ).2
  3. The number of permutations mapping D to a set closed under color i is at most |D|! * \binom{n/2}{|D|/2} * (n - |D|)!.

    The number of partial injections on D whose image is closed under color i is bounded by |D|! * \binom{n/2}{|D|/2} using w279_count_events and w279_count_closed (since color i forms a matching of size n/2). Decomposing the set of permutations fiberwise over φ, each fiber has size at most (n - |D|)! by w3_assignment_card. Summing over all fibers yields the product bound.

    lines 53–71

    uses w279_count_events, w279_count_closed, w279_card_R, Finset.card_eq_sum_card_fiberwise, smul_eq_mul, Finset.sum_const, Finset.sum_le_sum, w3_assignment_card, Nat.mul_le_mul_left, Nat.mul_le_mul_right

      have hF : F.card ≤ D.card.factorial * Nat.choose (n/2) (D.card/2) := by
        have hi := w279_count_events D (fun U => w279_closed c i U)
        have hc := w279_count_closed c m hm i D.card
        have hr : (w279_R c m i).card = n/2 := by have := w279_card_R c m hm i; omega
        rw [hr] at hc
        exact hi.trans (Nat.mul_le_mul_left _ hc)
      have hb : A.card ≤ F.card * (n-D.card).factorial := by
        rw [Finset.card_eq_sum_card_fiberwise (f := φ) (t := F) hmaps]
        rw [← smul_eq_mul, ← Finset.sum_const]
        refine Finset.sum_le_sum fun f hf => ?_
        have hfi := (Finset.mem_filter.1 hf).2.2.1
        refine (Finset.card_le_card ?_).trans (w3_assignment_card D f hfi)
        intro σ hσ
        rw [Finset.mem_filter] at hσ ⊢
        refine ⟨Finset.mem_univ _, ?_⟩
        intro x hx
        have he := congrFun hσ.2 x
        simpa only [φ, if_pos hx] using he
      exact hb.trans (Nat.mul_le_mul_right _ hF)
  4. For odd n ≥ 13, n * (12(n/2)(n-3)^{\underline 3} + 120(n/2)^3) < n^{\underline 6}. automation

    Writing n = 2r + 13 for r ≥ 0, we express both sides as explicit polynomials in r and verify the strict inequality using non-linear arithmetic (nlinarith) together with positivity of the difference.

    lines 76–84

    uses Nat.descFactorial_succ, Nat.descFactorial_zero, Nat.sub_zero, Nat.sub_sub

      obtain ⟨r,rfl⟩ : ∃ r : ℕ, n=2*r+13 := by exact ⟨(n-13)/2, by omega⟩
      have hm : (2*r+13)/2 = r+6 := by omega
      rw [hm]
      norm_num only [Nat.descFactorial_succ, Nat.descFactorial_zero, Nat.sub_zero, Nat.sub_sub]
      simp only [show 2*r+13-1=2*r+12 by omega, show 2*r+13-2=2*r+11 by omega,
        show 2*r+13-3=2*r+10 by omega, show 2*r+13-4=2*r+9 by omega,
        show 2*r+13-5=2*r+8 by omega]
      have hp : 0 < (2*r+13)*2*(r+6)*(16*r^4+256*r^3+1448*r^2+3140*r+1440) := by positivity
      nlinarith only [hp]
  5. For odd n ≥ 13, the total count of permutations making some cut closed is strictly less than n!.

    We factor out (n - 6)! from the expression n * (2 * 3! * \binom{n/2}{1} * (n - 3)! + 6! * \binom{n/2}{3} * (n - 6)!). Using \binom{n/2}{3} * 6! = 120 * (n/2)^{\underline 3} ≤ 120 * (n/2)^3, we bound the sum by (n - 6)! times the polynomial from w3_mass_polynomial, which is strictly less than (n - 6)! * n^{\underline 6} = n!.

    lines 89–102

    uses Nat.descFactorial_le_pow, Nat.descFactorial_eq_factorial_mul_choose, Nat.factorial_mul_descFactorial, w3_mass_polynomial, Nat.choose_one_right, Nat.mul_le_mul_left, Nat.mul_lt_mul_of_pos_left, Nat.factorial_pos

      have hc := Nat.descFactorial_le_pow (n/2) 3
      rw [Nat.descFactorial_eq_factorial_mul_choose] at hc
      norm_num only [Nat.factorial_succ, Nat.factorial_zero] at hc
      have h1 := Nat.factorial_mul_descFactorial (n := n) (k := 6) (by omega : 6 ≤ n)
      have h2 := Nat.factorial_mul_descFactorial (n := n-3) (k := 3) (by omega : 3 ≤ n-3)
      simp only [Nat.sub_sub, show 3+3=6 by decide] at h2
      have hp := w3_mass_polynomial n hn hodd
      calc _ ≤ (n-6).factorial * (n*(12*(n/2)*(n-3).descFactorial 3+120*(n/2)^3)) := by
              rw [← h2]
              norm_num only [Nat.factorial_succ, Nat.factorial_zero, Nat.choose_one_right]
              have hi := Nat.mul_le_mul_left (120*n*(n-6).factorial) hc
              nlinarith only [hi]
        _ < (n-6).factorial * n.descFactorial 6 := Nat.mul_lt_mul_of_pos_left hp (Nat.factorial_pos _)
        _ = _ := h1
  6. The block position sets have sizes |positions(0)| = 3, |positions(1)| = 3, and |positions(2)| = 6.

    We partition the first six vertices into blocks of size 3 and the remaining vertices into block 2. For each selector j, the positions set is explicitly identified by extensionality, and its cardinality is verified by counting elements.

    lines 107–133

    uses w3_sel, w3_positions, w3_block, Fin.ext_iff

    instance w3_sel_decidable (j b : Fin 3) : Decidable (w3_sel j b) := by unfold w3_sel; infer_instance
    
    def w3_positions (j : Fin 3) : Finset (Fin n) := Finset.univ.filter fun v => w3_sel j (w3_block v)
    
    lemma w3_mem_positions (j : Fin 3) (v : Fin n) : v ∈ w3_positions j ↔ w3_sel j (w3_block v) := by simp [w3_positions]
    
    lemma w3_positions_card (hn : 7 ≤ n) (j : Fin 3) :
        (w3_positions (n := n) j).card = if j=2 then 6 else 3 := by
      have he0 : w3_positions (n := n) 0 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩} := by
        ext v
        simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block,
          Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]
        split_ifs <;> omega
      have he1 : w3_positions (n := n) 1 = {⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by
        ext v
        simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block,
          Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]
        split_ifs <;> omega
      have he2 : w3_positions (n := n) 2 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩,⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by
        ext v
        simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block,
          Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]
        split_ifs <;> omega
      fin_cases j <;> norm_num [he0, he1, he2, Fin.ext_iff]
      change (w3_positions (n := n) 2).card = 6
      rw [he2]
      norm_num [Fin.ext_iff]
  7. The canonical roots satisfy w3_block(3j) = j, and every non-trivial cut in Fin 3 is selected by w3_sel j or its complement. automation

    Direct calculation confirms that vertex 3j belongs to block j. For the cut classification w3_cut_shape, the kernel decision procedure (decide +kernel) exhaustively checks all non-empty proper subsets of Fin 3.

    lines 135–142

    uses w3_block, Fin.ext_iff

    lemma w3_root (hn : 7 ≤ n) (j : Fin 3) :
        w3_block (⟨3*j.val, by have := j.isLt; omega⟩ : Fin n) = j := by
      fin_cases j <;> norm_num [w3_block, Fin.ext_iff]
    
    lemma w3_cut_shape : ∀ S : Finset (Fin 3), S.Nonempty → S ≠ Finset.univ →
        ∃ j : Fin 3, (∀ b : Fin 3, b ∈ S ↔ w3_sel j b) ∨
          (∀ b : Fin 3, b ∈ S ↔ ¬w3_sel j b) := by
      decide +kernel
  8. There exists a permutation σ such that no block position set is closed under any color.

    By the union bound, the number of permutations making some block position set closed under some color is at most the sum over all (j, i) of w3_closed_event_card. Substituting the cardinalities 3, 3, and 6, this sum is bounded by w3_mass_lt, which is strictly less than |S_n| = n!. Hence the bad permutations do not cover S_n, and a good permutation σ exists.

    lines 148–175

    uses Finset.card_biUnion_le, w3_closed_event_card, Fintype.sum_prod_type, w3_positions_card, Fin.sum_univ_succ, Finset.card_univ, Fintype.card_perm, Fintype.card_fin, w3_mass_lt, lt_irrefl, Finset.eq_univ_of_forall, Finset.mem_biUnion

      classical
      let Bad : Fin 3 × Fin n → Finset (Equiv.Perm (Fin n)) :=
        fun ji => Finset.univ.filter fun σ => w279_closed c ji.2 ((w3_positions (n := n) ji.1).image σ)
      let B : Finset (Equiv.Perm (Fin n)) := Finset.univ.biUnion Bad
      have hb : B.card ≤ n*(2*(3 : ℕ).factorial*Nat.choose (n/2) 1*(n-3).factorial+
          (6 : ℕ).factorial*Nat.choose (n/2) 3*(n-6).factorial) := by
        refine Finset.card_biUnion_le.trans ?_
        have hi : ∑ ji : Fin 3 × Fin n, (Bad ji).card ≤
            ∑ ji : Fin 3 × Fin n, (w3_positions (n := n) ji.1).card.factorial *
              Nat.choose (n/2) ((w3_positions (n := n) ji.1).card/2) * (n-(w3_positions (n := n) ji.1).card).factorial := by
          exact Finset.sum_le_sum fun ji hji => w3_closed_event_card c m hm (w3_positions (n := n) ji.1) ji.2
        refine hi.trans_eq ?_
        rw [Fintype.sum_prod_type]
        simp only [w3_positions_card (by omega : 7 ≤ n)]
        norm_num [Fin.sum_univ_succ, Fin.ext_iff]
        ring
      have hlt : B.card < (Finset.univ : Finset (Equiv.Perm (Fin n))).card := by
        rw [Finset.card_univ, Fintype.card_perm, Fintype.card_fin]
        exact hb.trans_lt (w3_mass_lt n hn hodd)
      have hne : B ≠ Finset.univ := by intro he; rw [he] at hlt; exact lt_irrefl _ hlt
      have hex : ∃ σ : Equiv.Perm (Fin n), σ ∉ B := by
        by_contra h
        push Not at h
        exact hne (Finset.eq_univ_of_forall h)
      obtain ⟨σ,hσ⟩ := hex
      refine ⟨σ, ?_⟩
      intro j i hi
      exact hσ (Finset.mem_biUnion.2 ⟨(j,i), Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _,hi⟩⟩)
  9. For odd n ≥ 13, there exists a 3-partition p with roots such that every color crosses every non-trivial cut.

    Using the good permutation σ from w3_avoid_blocks, we define p(v) = w3_block(σ^{-1}(v)) and roots(j) = σ(3j). If some color c(e) had no edge crossing cut S, the preimage under p would be closed under c(e). By w3_cut_shape, this preimage corresponds to σ(positions(j)) or its complement, which contradicts the choice of σ.

    lines 183–215

    uses w3_avoid_blocks, Equiv.symm_apply_apply, w3_root, w3_cut_shape, Finset.mem_image, w3_mem_positions, Ne.symm, w279_c_swap

      classical
      obtain ⟨σ,hσ⟩ := w3_avoid_blocks hn hodd c m hm
      refine ⟨(fun v => w3_block (σ.symm v)), (fun j => σ ⟨3*j.val, by have := j.isLt; omega⟩), ?_, ?_⟩
      · intro j
        simpa only [Equiv.symm_apply_apply] using w3_root (by omega : 7 ≤ n) j
      · intro e S hS hSu
        by_contra hno
        push Not at hno
        obtain ⟨j,hj | hj⟩ := w3_cut_shape S hS hSu
        · apply hσ j (c e)
          intro u hu v huv hc
          obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu
          have hxu := (w3_mem_positions j x).1 hx
          by_contra hv
          have hxS := (hj _).2 hxu
          have hvS : w3_block (σ.symm v) ∉ S := by
            intro hvS
            apply hv
            exact Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 ((hj _).1 hvS), by simp⟩
          exact hno (σ x) v huv (by simpa using hxS) hvS hc
        · apply hσ j (c e)
          intro u hu v huv hc
          obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu
          have hxu := (w3_mem_positions j x).1 hx
          by_contra hv
          have hxS : w3_block (σ.symm (σ x)) ∉ S := by
            intro hh
            exact (hj _).1 (by simpa using hh) hxu
          have hvS : w3_block (σ.symm v) ∈ S := by
            apply (hj _).2
            intro hvj
            exact hv (Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 hvj, by simp⟩)
          exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c huv).symm.trans hc)
  10. When n is odd and n ≥ 13, the wild number of K_n is at most n - 3 = (n - 4) + (n mod 2).

    For odd n, the chromatic index is k = n, and each color misses a unique vertex, yielding a bijection m. Applying w3_partition provides a 3-partition with roots where every color crosses every cut. By simple_graph_wild_number_le_of_block_cut_condition with q = 3, the wild number is at most n - 3.

    lines 221–227

    uses w279_missing_vertex_equiv, Fintype.card_congr, w3_partition, simple_graph_wild_number_le_of_block_cut_condition

      by_cases hodd : n%2=1
      · obtain ⟨m,hm⟩ := w279_missing_vertex_equiv n k (by omega) hodd hk c
        have hk' : k=n := by simpa using Fintype.card_congr m
        subst k
        obtain ⟨p,roots,hr,hc⟩ := w3_partition hn hodd c m hm
        have hu := simple_graph_wild_number_le_of_block_cut_condition (n := n) (q := 3) (by omega) c p roots hr hc
        omega
  11. When n is even and n ≥ 14, the wild number of K_n is at most n - 4 = (n - 4) + (n mod 2).

    When n is even, m = n - 1 ≥ 13 is odd, and the chromatic index is k = m. Restricting the coloring to K_m gives an m-coloring cc of K_m. Applying w3_partition on K_m yields a 3-partition crossing all cuts for all colors. We then lift this partition to K_n via wsc_even_upper_of_partition to conclude that the wild number of K_n is at most (m + 1) - 4 - 1 = n - 4.

    lines 228–243

    uses Nat.exists_eq_succ_of_ne_zero, wsc_even_min_colors, wsc_restrict_color, wsc_missing_vertex_equiv_of_le, w3_partition, wsc_color_used, wsc_even_upper_of_partition

      · obtain ⟨m,rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)
        have hm13 : 13 ≤ m := by omega
        have hmOdd : m%2=1 := by omega
        have hk' : k=m := wsc_even_min_colors (by omega) hmOdd hk c
        subst k
        let cc := wsc_restrict_color c
        obtain ⟨miss,hmiss⟩ := wsc_missing_vertex_equiv_of_le m m (by omega) hmOdd le_rfl cc
        obtain ⟨p,roots,hr,hcuts⟩ := w3_partition hm13 hmOdd cc miss hmiss
        have hc : ∀ (i : Fin m) (S : Finset (Fin 3)), S.Nonempty → S ≠ Finset.univ →
            ∃ (u v : Fin m) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ cc ⟨s(u,v),wild_kn_mem huv⟩ = i := by
          intro i S hS hSu
          obtain ⟨e,he⟩ := wsc_color_used (by omega) cc miss hmiss i
          obtain ⟨u,v,huv,hu,hv,hcol⟩ := hcuts e S hS hSu
          exact ⟨u,v,huv,hu,hv,hcol.trans he⟩
        have hu := wsc_even_upper_of_partition (by omega) c p roots hr hc
        omega
permutation_partial_assignment_card_bound_of_switching
The number of permutations extending an injective map on a subset D multiplied by n^{\underline{|D|}} is at most the total number of permutations.
Nat.factorial_mul_descFactorial
For k ≤ n, (n - k)! * n^{\underline k} = n!.
Nat.descFactorial_pos
The falling factorial n^{\underline k} is strictly positive if and only if k ≤ n.
Nat.le_of_mul_le_mul_left
If c * a ≤ c * b and c > 0, then a ≤ b.
Nat.mul_comm
Multiplication of natural numbers is commutative.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the cardinality of the type.
if_neg
If a boolean condition is false, the conditional expression reduces to the else branch.
if_pos
If a boolean condition is true, the conditional expression reduces to the then branch.
Finset.image_congr
If two functions agree pointwise on a set, their images of that set are equal.
w279_count_events
The number of partial injections on D whose image satisfies property P is at most |D|! times the number of subsets of size |D| satisfying P.
w279_count_closed
The number of subsets of size s closed under color i in a near-factored complete graph is at most \binom{|R_i|}{s/2}.
w279_card_R
The size of the color matching R_i satisfies n = 2|R_i| + 1, so |R_i| = n/2.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of its fibers under any mapping.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set times the constant.
Finset.sum_le_sum
If f(x) ≤ g(x) for all x in a finite set, the sum of f is at most the sum of g.
w3_assignment_card
The number of permutations extending an injective map on D is at most (n - |D|)!.
Nat.mul_le_mul_left
If a ≤ b, then c * a ≤ c * b.
Nat.mul_le_mul_right
If a ≤ b, then a * c ≤ b * c.
Nat.descFactorial_succ
The falling factorial satisfies n^{\underline{k+1}} = (n - k) * n^{\underline k}.
Nat.descFactorial_zero
The falling factorial of length 0 is 1.
Nat.sub_zero
Subtracting zero leaves a natural number unchanged.
Nat.sub_sub
Subtracting m then k equals subtracting m + k.
Nat.descFactorial_le_pow
The falling factorial n^{\underline k} is bounded above by n^k.
Nat.descFactorial_eq_factorial_mul_choose
The falling factorial satisfies n^{\underline k} = k! * \binom{n}{k}.
w3_mass_polynomial
For odd n ≥ 13, n * (12(n/2)(n-3)^{\underline 3} + 120(n/2)^3) < n^{\underline 6}.
Nat.choose_one_right
\binom{n}{1} = n for every natural number n.
Nat.mul_lt_mul_of_pos_left
If a < b and c > 0, then c * a < c * b.
Nat.factorial_pos
The factorial of any natural number is strictly positive.
w3_sel
Predicate defining which vertex blocks belong to selector j in Fin 3.
w3_positions
The set of vertices whose block index satisfies selector j.
w3_block
The canonical assignment of each vertex in Fin n to block 0, 1, or 2.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying integers are equal.
Finset.card_biUnion_le
The cardinality of a union of finite sets is at most the sum of their cardinalities.
w3_closed_event_card
The number of permutations mapping D to a set closed under color i is at most |D|! * \binom{n/2}{|D|/2} * (n - |D|)!.
Fintype.sum_prod_type
A sum over a product of two finite types equals the iterated sum over each component.
w3_positions_card
For n ≥ 7, the size of positions(j) is 6 if j = 2, and 3 otherwise.
Fin.sum_univ_succ
A sum over Fin (n+1) splits as the term at 0 plus the sum over the remaining terms.
Finset.card_univ
The cardinality of the universal set of a finite type equals the type's cardinality.
Fintype.card_perm
The permutation group of a set of size n has cardinality n!.
Fintype.card_fin
The cardinality of Fin n is n.
w3_mass_lt
For odd n ≥ 13, the sum of bad permutation counts over all colors and block cuts is strictly less than n!.
lt_irrefl
Strict inequality is irreflexive: no element is strictly less than itself.
Finset.eq_univ_of_forall
A subset containing every element of a finite type is the entire universe.
Finset.mem_biUnion
An element belongs to a big union iff it belongs to one of the indexed members.
w3_avoid_blocks
There exists a permutation σ such that no block position set under σ is closed under any color.
Equiv.symm_apply_apply
Applying an equivalence and then its inverse is the identity.
w3_root
The canonical representative 3j of part j belongs to block j.
w3_cut_shape
Every non-trivial cut in a 3-element set is either a standard selector or its complement.
Finset.mem_image
An element is in the image of a set iff it is the value of some element in that set.
w3_mem_positions
A vertex belongs to positions(j) iff its block satisfies selector j.
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
w279_c_swap
Swapping the two endpoints of an edge does not change its color.
w279_missing_vertex_equiv
In a proper edge coloring of odd K_n with minimal colors, every color misses a unique vertex.
Fintype.card_congr
Equivalent finite types have equal cardinality.
w3_partition
For odd n ≥ 13, there exists a 3-partition with roots where every color crosses every cut.
simple_graph_wild_number_le_of_block_cut_condition
A graph coloring with a q-partition and roots where every color crosses every cut has wild number at most n - q.
Nat.exists_eq_succ_of_ne_zero
Every non-zero natural number is a successor of some natural number.
wsc_even_min_colors
For odd n ≥ 3, the chromatic number of the line graph of K_n is n.
wsc_restrict_color
Restricts an edge coloring of K_{m+1} to an edge coloring of the complete subgraph K_m.
wsc_missing_vertex_equiv_of_le
A proper edge coloring of odd K_m with at most m colors induces a bijection between colors and missing vertices.
wsc_color_used
Every color is used by at least one edge in a proper edge coloring of complete graphs with missing vertex bijection.
wsc_even_upper_of_partition
For even n, a 3-partition of the odd subgraph K_{n-1} crossing all cuts implies the wild number of K_n is at most n - 4.

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 100000variable {n : ℕ}open Classical inlemma w3_assignment_card (D : Finset (Fin n)) (f : Fin n → Fin n)    (hf : Set.InjOn f (↑D : Set (Fin n))) :    (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => ∀ x ∈ D, σ x = f x)).card ≤ (n-D.card).factorial := by  classical  have hi := permutation_partial_assignment_card_bound_of_switching D f hf    (Finset.univ : Finset (Equiv.Perm (Fin n))) (by intro a ha σ hσ hσa y; exact Finset.mem_univ _)  simp only [Fintype.card_fin, Finset.card_univ, Fintype.card_perm] at hi  have hd : D.card ≤ n := by simpa using Finset.card_le_univ D  have he := Nat.factorial_mul_descFactorial hd  have hp : 0 < (n : ℕ).descFactorial D.card := Nat.descFactorial_pos.2 hd  apply Nat.le_of_mul_le_mul_left (c := (n : ℕ).descFactorial D.card) (hc := hp)  convert hi.trans_eq (he.symm.trans (Nat.mul_comm _ _)) using 1  congr 1  apply congrArg Finset.card  ext σ  simp only [Finset.mem_filter, Finset.mem_univ, true_and]open Classical inlemma w3_closed_event_card    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n))    (m : Fin n ≃ Fin n)    (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i)    (D : Finset (Fin n)) (i : Fin n) :    (Finset.univ.filter (fun σ : Equiv.Perm (Fin n) => w279_closed c i (D.image σ))).card ≤      D.card.factorial * Nat.choose (n/2) (D.card/2) * (n-D.card).factorial := by  classical  let A : Finset (Equiv.Perm (Fin n)) := Finset.univ.filter fun σ => w279_closed c i (D.image σ)  let F : Finset (Fin n → Fin n) := Finset.univ.filter fun f =>    (∀ x ∉ D, f x = x) ∧ Set.InjOn f (↑D : Set (Fin n)) ∧ w279_closed c i (D.image f)  let φ : Equiv.Perm (Fin n) → Fin n → Fin n := fun σ x => if x ∈ D then σ x else x  have hmaps : ∀ σ ∈ A, φ σ ∈ F := by    intro σ hσ    simp only [F, Finset.mem_filter, Finset.mem_univ, true_and]    refine ⟨?_, ?_, ?_⟩    · intro x hx; simp only [φ, if_neg hx]    · intro x hx y hy he      change x ∈ D at hx      change y ∈ D at hy      dsimp only [φ] at he      rw [if_pos hx, if_pos hy] at he      exact σ.injective he    · have he : D.image (φ σ) = D.image σ := by        apply Finset.image_congr        intro x hx        change x ∈ D at hx        simp only [φ, if_pos hx]      rw [he]      exact (Finset.mem_filter.1 hσ).2  have hF : F.card ≤ D.card.factorial * Nat.choose (n/2) (D.card/2) := by    have hi := w279_count_events D (fun U => w279_closed c i U)    have hc := w279_count_closed c m hm i D.card    have hr : (w279_R c m i).card = n/2 := by have := w279_card_R c m hm i; omega    rw [hr] at hc    exact hi.trans (Nat.mul_le_mul_left _ hc)  have hb : A.card ≤ F.card * (n-D.card).factorial := by    rw [Finset.card_eq_sum_card_fiberwise (f := φ) (t := F) hmaps]    rw [← smul_eq_mul, ← Finset.sum_const]    refine Finset.sum_le_sum fun f hf => ?_    have hfi := (Finset.mem_filter.1 hf).2.2.1    refine (Finset.card_le_card ?_).trans (w3_assignment_card D f hfi)    intro σ hσ    rw [Finset.mem_filter] at hσ ⊢    refine ⟨Finset.mem_univ _, ?_⟩    intro x hx    have he := congrFun hσ.2 x    simpa only [φ, if_pos hx] using he  exact hb.trans (Nat.mul_le_mul_right _ hF)lemma w3_mass_polynomial (n : ℕ) (hn : 13 ≤ n) (hodd : n % 2 = 1) :    n*(12*(n/2)*(n-3).descFactorial 3+120*(n/2)^3) < n.descFactorial 6 := by  obtain ⟨r,rfl⟩ : ∃ r : ℕ, n=2*r+13 := by exact ⟨(n-13)/2, by omega⟩  have hm : (2*r+13)/2 = r+6 := by omega  rw [hm]  norm_num only [Nat.descFactorial_succ, Nat.descFactorial_zero, Nat.sub_zero, Nat.sub_sub]  simp only [show 2*r+13-1=2*r+12 by omega, show 2*r+13-2=2*r+11 by omega,    show 2*r+13-3=2*r+10 by omega, show 2*r+13-4=2*r+9 by omega,    show 2*r+13-5=2*r+8 by omega]  have hp : 0 < (2*r+13)*2*(r+6)*(16*r^4+256*r^3+1448*r^2+3140*r+1440) := by positivity  nlinarith only [hp]lemma w3_mass_lt (n : ℕ) (hn : 13 ≤ n) (hodd : n % 2 = 1) :    n*(2*(3 : ℕ).factorial*Nat.choose (n/2) 1*(n-3).factorial+      (6 : ℕ).factorial*Nat.choose (n/2) 3*(n-6).factorial) < n.factorial := by  have hc := Nat.descFactorial_le_pow (n/2) 3  rw [Nat.descFactorial_eq_factorial_mul_choose] at hc  norm_num only [Nat.factorial_succ, Nat.factorial_zero] at hc  have h1 := Nat.factorial_mul_descFactorial (n := n) (k := 6) (by omega : 6 ≤ n)  have h2 := Nat.factorial_mul_descFactorial (n := n-3) (k := 3) (by omega : 3 ≤ n-3)  simp only [Nat.sub_sub, show 3+3=6 by decide] at h2  have hp := w3_mass_polynomial n hn hodd  calc _ ≤ (n-6).factorial * (n*(12*(n/2)*(n-3).descFactorial 3+120*(n/2)^3)) := by          rw [← h2]          norm_num only [Nat.factorial_succ, Nat.factorial_zero, Nat.choose_one_right]          have hi := Nat.mul_le_mul_left (120*n*(n-6).factorial) hc          nlinarith only [hi]    _ < (n-6).factorial * n.descFactorial 6 := Nat.mul_lt_mul_of_pos_left hp (Nat.factorial_pos _)    _ = _ := h1def w3_block (v : Fin n) : Fin 3 := if v.val<3 then 0 else if v.val<6 then 1 else 2def w3_sel (j b : Fin 3) : Prop := if j=0 then b=0 else if j=1 then b=1 else b≠2instance w3_sel_decidable (j b : Fin 3) : Decidable (w3_sel j b) := by unfold w3_sel; infer_instancedef w3_positions (j : Fin 3) : Finset (Fin n) := Finset.univ.filter fun v => w3_sel j (w3_block v)lemma w3_mem_positions (j : Fin 3) (v : Fin n) : v ∈ w3_positions j ↔ w3_sel j (w3_block v) := by simp [w3_positions]lemma w3_positions_card (hn : 7 ≤ n) (j : Fin 3) :    (w3_positions (n := n) j).card = if j=2 then 6 else 3 := by  have he0 : w3_positions (n := n) 0 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩} := by    ext v    simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block,      Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]    split_ifs <;> omega  have he1 : w3_positions (n := n) 1 = {⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by    ext v    simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block,      Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]    split_ifs <;> omega  have he2 : w3_positions (n := n) 2 = {⟨0,by omega⟩,⟨1,by omega⟩,⟨2,by omega⟩,⟨3,by omega⟩,⟨4,by omega⟩,⟨5,by omega⟩} := by    ext v    simp only [w3_positions, Finset.mem_filter, Finset.mem_univ, true_and, w3_sel, w3_block,      Finset.mem_insert, Finset.mem_singleton, Fin.ext_iff]    split_ifs <;> omega  fin_cases j <;> norm_num [he0, he1, he2, Fin.ext_iff]  change (w3_positions (n := n) 2).card = 6  rw [he2]  norm_num [Fin.ext_iff]lemma w3_root (hn : 7 ≤ n) (j : Fin 3) :    w3_block (⟨3*j.val, by have := j.isLt; omega⟩ : Fin n) = j := by  fin_cases j <;> norm_num [w3_block, Fin.ext_iff]lemma w3_cut_shape : ∀ S : Finset (Fin 3), S.Nonempty → S ≠ Finset.univ →    ∃ j : Fin 3, (∀ b : Fin 3, b ∈ S ↔ w3_sel j b) ∨      (∀ b : Fin 3, b ∈ S ↔ ¬w3_sel j b) := by  decide +kernellemma w3_avoid_blocks (hn : 13 ≤ n) (hodd : n % 2 = 1)    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n)    (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) :    ∃ σ : Equiv.Perm (Fin n), ∀ (j : Fin 3) (i : Fin n), ¬w279_closed c i ((w3_positions j).image σ) := by  classical  let Bad : Fin 3 × Fin n → Finset (Equiv.Perm (Fin n)) :=    fun ji => Finset.univ.filter fun σ => w279_closed c ji.2 ((w3_positions (n := n) ji.1).image σ)  let B : Finset (Equiv.Perm (Fin n)) := Finset.univ.biUnion Bad  have hb : B.card ≤ n*(2*(3 : ℕ).factorial*Nat.choose (n/2) 1*(n-3).factorial+      (6 : ℕ).factorial*Nat.choose (n/2) 3*(n-6).factorial) := by    refine Finset.card_biUnion_le.trans ?_    have hi : ∑ ji : Fin 3 × Fin n, (Bad ji).card ≤        ∑ ji : Fin 3 × Fin n, (w3_positions (n := n) ji.1).card.factorial *          Nat.choose (n/2) ((w3_positions (n := n) ji.1).card/2) * (n-(w3_positions (n := n) ji.1).card).factorial := by      exact Finset.sum_le_sum fun ji hji => w3_closed_event_card c m hm (w3_positions (n := n) ji.1) ji.2    refine hi.trans_eq ?_    rw [Fintype.sum_prod_type]    simp only [w3_positions_card (by omega : 7 ≤ n)]    norm_num [Fin.sum_univ_succ, Fin.ext_iff]    ring  have hlt : B.card < (Finset.univ : Finset (Equiv.Perm (Fin n))).card := by    rw [Finset.card_univ, Fintype.card_perm, Fintype.card_fin]    exact hb.trans_lt (w3_mass_lt n hn hodd)  have hne : B ≠ Finset.univ := by intro he; rw [he] at hlt; exact lt_irrefl _ hlt  have hex : ∃ σ : Equiv.Perm (Fin n), σ ∉ B := by    by_contra h    push Not at h    exact hne (Finset.eq_univ_of_forall h)  obtain ⟨σ,hσ⟩ := hex  refine ⟨σ, ?_⟩  intro j i hi  exact hσ (Finset.mem_biUnion.2 ⟨(j,i), Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _,hi⟩⟩)lemma w3_partition (hn : 13 ≤ n) (hodd : n % 2 = 1)    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n)    (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v,w),wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) :    ∃ (p : Fin n → Fin 3) (roots : Fin 3 → Fin n), (∀ t, p (roots t) = t) ∧      ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin 3)), S.Nonempty → S ≠ Finset.univ →        ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by  classical  obtain ⟨σ,hσ⟩ := w3_avoid_blocks hn hodd c m hm  refine ⟨(fun v => w3_block (σ.symm v)), (fun j => σ ⟨3*j.val, by have := j.isLt; omega⟩), ?_, ?_⟩  · intro j    simpa only [Equiv.symm_apply_apply] using w3_root (by omega : 7 ≤ n) j  · intro e S hS hSu    by_contra hno    push Not at hno    obtain ⟨j,hj | hj⟩ := w3_cut_shape S hS hSu    · apply hσ j (c e)      intro u hu v huv hc      obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu      have hxu := (w3_mem_positions j x).1 hx      by_contra hv      have hxS := (hj _).2 hxu      have hvS : w3_block (σ.symm v) ∉ S := by        intro hvS        apply hv        exact Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 ((hj _).1 hvS), by simp⟩      exact hno (σ x) v huv (by simpa using hxS) hvS hc    · apply hσ j (c e)      intro u hu v huv hc      obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu      have hxu := (w3_mem_positions j x).1 hx      by_contra hv      have hxS : w3_block (σ.symm (σ x)) ∉ S := by        intro hh        exact (hj _).1 (by simpa using hh) hxu      have hvS : w3_block (σ.symm v) ∈ S := by        apply (hj _).2        intro hvj        exact hv (Finset.mem_image.2 ⟨σ.symm v, (w3_mem_positions _ _).2 hvj, by simp⟩)      exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c huv).symm.trans hc)theorem wild_number_complete_graph_upper_sub_four_add_parity (n k : ℕ) (hn : 13 ≤ n)    (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) :    simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c ≤ n-4+n%2 := by  by_cases hodd : n%2=1  · obtain ⟨m,hm⟩ := w279_missing_vertex_equiv n k (by omega) hodd hk c    have hk' : k=n := by simpa using Fintype.card_congr m    subst k    obtain ⟨p,roots,hr,hc⟩ := w3_partition hn hodd c m hm    have hu := simple_graph_wild_number_le_of_block_cut_condition (n := n) (q := 3) (by omega) c p roots hr hc    omega  · obtain ⟨m,rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)    have hm13 : 13 ≤ m := by omega    have hmOdd : m%2=1 := by omega    have hk' : k=m := wsc_even_min_colors (by omega) hmOdd hk c    subst k    let cc := wsc_restrict_color c    obtain ⟨miss,hmiss⟩ := wsc_missing_vertex_equiv_of_le m m (by omega) hmOdd le_rfl cc    obtain ⟨p,roots,hr,hcuts⟩ := w3_partition hm13 hmOdd cc miss hmiss    have hc : ∀ (i : Fin m) (S : Finset (Fin 3)), S.Nonempty → S ≠ Finset.univ →        ∃ (u v : Fin m) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ cc ⟨s(u,v),wild_kn_mem huv⟩ = i := by      intro i S hS hSu      obtain ⟨e,he⟩ := wsc_color_used (by omega) cc miss hmiss i      obtain ⟨u,v,huv,hu,hv,hcol⟩ := hcuts e S hS hSu      exact ⟨u,v,huv,hu,hv,hcol.trans he⟩    have hu := wsc_even_upper_of_partition (by omega) c p roots hr hc    omega
See it in the graphDiscuss this resultChallenge it