wild_number_complete_graph_formula_iff_odd_orders
The wild-number sharpness conjecture for minimum proper colorings of every complete graph of order at least three is equivalent to its restriction to odd orders at least three.
Statement
theorem wild_number_complete_graph_formula_iff_odd_orders :
(∀ (n k : ℕ), 3 ≤ n →
(⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k →
∀ c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k),
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4*((n+1)/2)/3) ↔
(∀ (n k : ℕ), 3 ≤ n → n%2=1 →
(⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k →
∀ c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k),
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4*((n+1)/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 3
- wild_number_complete_even_eq_of_preceding_oddFor 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…
- 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.
The proof, explained
The equivalence between the conjecture for all complete graphs $K_n$ ($n \ge 3$) and its restriction to odd orders is proved by splitting into both implications. The forward implication is trivial by specializing the universal hypothesis to odd orders. For the converse, an odd order holds immediately by assumption, while an even order $n$ is written as $m + 1$ for an odd integer $m \ge 3$, allowing the result for $K_m$ to be transferred to $K_{m+1} = K_n$ via a known reduction lemma.
The forward direction holds: if the formula holds for all complete graphs of order at least 3, it holds in particular for all odd orders at least 3.
Splitting the equivalence into two implications, the forward direction is immediate by specializing the universal hypothesis over all $n \ge 3$ to odd $n$, discarding the redundant assumption that $n$ is odd.
constructor · intro h n k hn _ hk c exact h n k hn hk c
For the reverse direction, the formula holds whenever $n$ is odd.
Assuming the formula holds for all odd orders at least 3, we take an arbitrary $n \ge 3$, line-graph chromatic number $k$, and proper coloring $c$. We split on the parity of $n$: if $n$ is odd ($n \% 2 = 1$), the conclusion follows directly from the assumption.
· intro h n k hn hk c by_cases hodd : n%2=1 · exact h n k hn hodd hk c
When $n$ is even, $n$ can be written as $m + 1$ with $m \ge 3$ and $m$ odd.
Since $n \ge 3$, $n \ne 0$, so `Nat.exists_eq_succ_of_ne_zero` yields a predecessor $m$ such that $n = m + 1$. Because $n \ge 3$ and $n$ is not odd, linear arithmetic (`omega`) establishes that $m \ge 3$ and $m$ is odd ($m \% 2 = 1$).
uses
Nat.exists_eq_succ_of_ne_zero· obtain ⟨m,rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n≠0) have hm : 3 ≤ m := by omega have hmOdd : m%2=1 := by omega
Every proper coloring of the line graph of $K_m$ using $m$ colors satisfies the wild number formula.
By lemma `complete_graph_odd_line_graph_chromatic_number_eq`, the chromatic number of the line graph of $K_m$ is $m$ for odd $m \ge 3$. Applying the assumed odd-order hypothesis to $m$ with chromatic number $m$ shows that every proper $m$-coloring of the line graph of $K_m$ achieves the wild number formula.
uses
complete_graph_odd_line_graph_chromatic_number_eqhave hsharp : ∀ cc : (⊤ : SimpleGraph (Fin m)).lineGraph.Coloring (Fin m), simple_graph_wild_number (⊤ : SimpleGraph (Fin m)) cc = 4*((m+1)/2)/3 := by intro cc exact h m m hm hmOdd (complete_graph_odd_line_graph_chromatic_number_eq m hm hmOdd) cc
The wild number formula holds for the even order $n = m + 1$.
Lemma `wild_number_complete_even_eq_of_preceding_odd` establishes that if the wild number formula holds for all minimum colorings of the line graph of $K_m$ ($m$ odd, $m \ge 3$), it also holds for every minimum coloring of the line graph of $K_{m+1} = K_n$.
uses
wild_number_complete_even_eq_of_preceding_oddexact wild_number_complete_even_eq_of_preceding_odd m k hm hmOdd hsharp hk c
Nat.exists_eq_succ_of_ne_zero- Every non-zero natural number is the successor of some natural number ($n = m + 1$).
complete_graph_odd_line_graph_chromatic_number_eq- For any odd order $n \ge 3$, the chromatic number of the line graph of the complete graph $K_n$ equals $n$.
wild_number_complete_even_eq_of_preceding_odd- If the wild number formula holds for all minimum colorings of the line graph of $K_n$ with $n \ge 3$ odd, then it also holds for every minimum coloring of the line graph of $K_{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_graph_formula_iff_odd_orders : (∀ (n k : ℕ), 3 ≤ n → (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k → ∀ c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k), simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4*((n+1)/2)/3) ↔ (∀ (n k : ℕ), 3 ≤ n → n%2=1 → (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k → ∀ c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k), simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 4*((n+1)/2)/3) := by constructor · intro h n k hn _ hk c exact h n k hn hk c · intro h n k hn hk c by_cases hodd : n%2=1 · exact h n k hn hodd hk c · obtain ⟨m,rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n≠0) have hm : 3 ≤ m := by omega have hmOdd : m%2=1 := by omega have hsharp : ∀ cc : (⊤ : SimpleGraph (Fin m)).lineGraph.Coloring (Fin m), simple_graph_wild_number (⊤ : SimpleGraph (Fin m)) cc = 4*((m+1)/2)/3 := by intro cc exact h m m hm hmOdd (complete_graph_odd_line_graph_chromatic_number_eq m hm hmOdd) cc exact wild_number_complete_even_eq_of_preceding_odd m k hm hmOdd hsharp hk c