wild_number_complete_even_eq_of_preceding_odd
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
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
- wild_number_complete_odd_eq_iff_optimal_partitionFor every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted…
- complete_graph_odd_line_graph_chromatic_number_eqThe edge chromatic number of an odd complete graph on at least three vertices is its number of vertices.
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- Used by 1
- wild_number_complete_graph_formula_iff_odd_ordersThe wild-number sharpness conjecture for minimum proper colorings of every complete graph of order at least three is equivalent to its…
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.
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.
uses
wsc_even_min_colorshave hkn := wsc_even_min_colors hn hodd hk c subst k
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.
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_rfllet 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
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.
uses
wsc_color_used,wild_kn_memhave 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⟩
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.
uses
wsc_even_upper_of_partitionhave 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
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.
uses
le_antisymm,wild_number_complete_graph_min_proper_coloring_geexact 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.
- In lines 22, 23, and 25, linear integer arithmetic (`omega`) automatically discharges the side conditions 0 < n, n - n / 3 = 4 * ((n + 2) / 2) / 3 for odd n, and 3 ≤ n + 1.
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.
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)