AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_even_eq_of_preceding_odd

theoremverified

For odd n>=3, if every proper n-coloring of K_n has the conjectured sharp wild number, then every minimum proper coloring of K_(n+1) has the conjectured sharp wild number.

Statement

theorem wild_number_complete_even_eq_of_preceding_odd (n k : ℕ) (hn : 3 ≤ n) (hodd : n%2=1)
    (hsharp : ∀ cc : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n),
      simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) cc = 4*((n+1)/2)/3)
    (hk : (⊤ : SimpleGraph (Fin (n+1))).lineGraph.chromaticNumber = k)
    (c : (⊤ : SimpleGraph (Fin (n+1))).lineGraph.Coloring (Fin k)) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin (n+1))) c = 4*((n+2)/2)/3
Source
General parity reduction for the OP-306 campaign, related to arXiv:2610.22142 Section3.3.3 and the existing deleted-vertex partition-lifting proof. This is a conditional transfer and equivalence, not an assertion that the unresolved odd-order cases hold.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The proof establishes matching upper and lower bounds on the wild number of any minimum proper edge coloring c of K_(n+1) when n ≥ 3 is odd. Because n+1 is even, the chromatic index of K_(n+1) is k = n, so restricting c to K_n yields a proper n-coloring of K_n. By hypothesis, this restriction achieves the conjectured sharp wild number for K_n, which is equivalent to the existence of an optimal partition of K_n into n/3 parts where every color crosses every non-trivial cut. This partition induces an upper bound of n - n/3 = 4*((n+2)/2)/3 on the wild number of c on K_(n+1), which coincides with the general lower bound and concludes the equality.

  1. The chromatic index of K_(n+1) is k = n, so c is an n-coloring.

    Since n ≥ 3 is odd, K_(n+1) has an even number of vertices and its chromatic index is n. The lemma `wsc_even_min_colors` deduces k = n from the assumption hk that k is the chromatic number of the line graph of K_(n+1), and `subst k` substitutes n for k throughout.

    lines 10–11

    uses wsc_even_min_colors

      have hkn := wsc_even_min_colors hn hodd hk c
      subst k
  2. Restricting c to K_n gives an n-coloring cc that admits an optimal partition into n/3 parts with the cut-crossing property.

    Restricting c to K_n via `wsc_restrict_color` produces an n-coloring cc of K_n. Since n is odd, the chromatic index of K_n is n by `complete_graph_odd_line_graph_chromatic_number_eq`. By the hypothesis `hsharp`, cc achieves the sharp wild number, so `wild_number_complete_odd_eq_iff_optimal_partition` produces a partition p : Fin n → Fin (n/3) with section r, each fiber of size at least 3, such that every edge color in cc crosses every non-trivial cut. Finally, `wsc_missing_vertex_equiv_of_le` (applied with `le_rfl`) gives a bijection m between colors and their unique missing vertices in K_n.

    lines 12–15

    uses wsc_restrict_color, complete_graph_odd_line_graph_chromatic_number_eq, wild_number_complete_odd_eq_iff_optimal_partition, wsc_missing_vertex_equiv_of_le, le_rfl

      let cc := wsc_restrict_color c
      have hkodd := complete_graph_odd_line_graph_chromatic_number_eq n hn hodd
      obtain ⟨p,r,hr,hmin,hcut⟩ := (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hkodd cc).1 (hsharp cc)
      obtain ⟨m,hm⟩ := wsc_missing_vertex_equiv_of_le n n hn hodd le_rfl cc
  3. Every color in Fin n crosses every non-trivial cut of the partition p in K_n.

    Given a color i and a non-empty proper subset S of Fin (n/3), `wsc_color_used` guarantees that color i is assigned to some edge e of K_n. Applying the partition cut property `hcut` to e and S gives two vertices u, v crossing S whose edge (valid by `wild_kn_mem`) has color cc e = i.

    lines 16–21

    uses wsc_color_used, wild_kn_mem

      have hcuts : ∀ (i : Fin n) (S : Finset (Fin (n/3))), S.Nonempty → S ≠ Finset.univ →
          ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ cc ⟨s(u,v),wild_kn_mem huv⟩ = i := by
        intro i S hS hproper
        obtain ⟨e,he⟩ := wsc_color_used hn cc m hm i
        obtain ⟨u,v,huv,hu,hv,hc⟩ := hcut e S hS hproper
        exact ⟨u,v,huv,hu,hv,hc.trans he⟩
  4. The wild number of c on K_(n+1) is at most 4*((n+2)/2)/3.

    By `wsc_even_upper_of_partition` (with 0 < n proved by `omega`), the existence of the partition p and the cut condition `hcuts` bounds the wild number of c by n - n/3. For odd n, the arithmetic identity n - n/3 = 4*((n+2)/2)/3 is verified by `omega`, giving the required upper bound hu.

    lines 22–24

    uses wsc_even_upper_of_partition

      have hu := wsc_even_upper_of_partition (by omega) c p r hr hcuts
      have he : n-n/3 = 4*((n+2)/2)/3 := by omega
      rw [he] at hu
  5. The wild number of c on K_(n+1) equals 4*((n+2)/2)/3.

    By `wild_number_complete_graph_min_proper_coloring_ge`, every minimum proper edge coloring of K_(n+1) has wild number at least 4*(((n+1)+1)/2)/3 = 4*((n+2)/2)/3 (with 3 ≤ n+1 proved by `omega`). Combining this lower bound with the upper bound hu via `le_antisymm` yields the equality.

    line 25

    uses le_antisymm, wild_number_complete_graph_min_proper_coloring_ge

      exact le_antisymm hu (wild_number_complete_graph_min_proper_coloring_ge (n+1) n (by omega) hk c)
wsc_even_min_colors
For an odd integer n ≥ 3, the chromatic number of the line graph of K_(n+1) is n, so any minimum proper edge coloring of K_(n+1) uses exactly n colors.
wsc_restrict_color
Restricts an edge coloring of K_(n+1) to the subgraph K_n via the standard vertex inclusion.
complete_graph_odd_line_graph_chromatic_number_eq
For an odd integer n ≥ 3, the chromatic index (line graph chromatic number) of K_n is n.
wild_number_complete_odd_eq_iff_optimal_partition
For odd n ≥ 3, a proper k-coloring of K_n achieves the sharp wild number 4*((n+1)/2)/3 if and only if there exists a partition of the vertices into n/3 parts of size at least 3 such that every non-trivial cut is crossed by an edge of each color appearing in the coloring.
wsc_missing_vertex_equiv_of_le
In an edge coloring of K_n (n ≥ 3 odd) with at most n colors, each color is missing at exactly one vertex, yielding a bijection between colors and missing vertices.
le_rfl
Reflexivity of the ordering relation (here n ≤ n).
wild_kn_mem
For distinct vertices u ≠ v in a complete graph, the unordered pair s(u, v) is an edge.
wsc_color_used
In a proper n-coloring of K_n (n ≥ 3) where each color misses a unique vertex, every color is used on at least one edge.
wsc_even_upper_of_partition
Given an edge coloring c of K_(n+1) with n colors and a partition of K_n into q parts such that every non-trivial cut contains edges of every color under the restricted coloring, the wild number of c on K_(n+1) is at most n - q.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
wild_number_complete_graph_min_proper_coloring_ge
Any minimum proper edge coloring of K_n (n ≥ 3) has wild number at least 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 Classicalset_option maxHeartbeats 1000000theorem wild_number_complete_even_eq_of_preceding_odd (n k : ℕ) (hn : 3 ≤ n) (hodd : n%2=1)    (hsharp : ∀ cc : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n),      simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) cc = 4*((n+1)/2)/3)    (hk : (⊤ : SimpleGraph (Fin (n+1))).lineGraph.chromaticNumber = k)    (c : (⊤ : SimpleGraph (Fin (n+1))).lineGraph.Coloring (Fin k)) :    simple_graph_wild_number (⊤ : SimpleGraph (Fin (n+1))) c = 4*((n+2)/2)/3 := by  have hkn := wsc_even_min_colors hn hodd hk c  subst k  let cc := wsc_restrict_color c  have hkodd := complete_graph_odd_line_graph_chromatic_number_eq n hn hodd  obtain ⟨p,r,hr,hmin,hcut⟩ := (wild_number_complete_odd_eq_iff_optimal_partition hn hodd hkodd cc).1 (hsharp cc)  obtain ⟨m,hm⟩ := wsc_missing_vertex_equiv_of_le n n hn hodd le_rfl cc  have hcuts : ∀ (i : Fin n) (S : Finset (Fin (n/3))), S.Nonempty → S ≠ Finset.univ →      ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ cc ⟨s(u,v),wild_kn_mem huv⟩ = i := by    intro i S hS hproper    obtain ⟨e,he⟩ := wsc_color_used hn cc m hm i    obtain ⟨u,v,huv,hu,hv,hc⟩ := hcut e S hS hproper    exact ⟨u,v,huv,hu,hv,hc.trans he⟩  have hu := wsc_even_upper_of_partition (by omega) c p r hr hcuts  have he : n-n/3 = 4*((n+2)/2)/3 := by omega  rw [he] at hu  exact le_antisymm hu (wild_number_complete_graph_min_proper_coloring_ge (n+1) n (by omega) hk c)
See it in the graphDiscuss this resultChallenge it