wild_number_complete_thirteen_fourteen_eq_nine_or_ten
For n=13 or n=14, every minimum proper edge coloring of K_n has wild number either 9 or 10.
Statement
theorem wild_number_complete_thirteen_fourteen_eq_nine_or_ten (n k : ℕ) (hn : n = 13 ∨ n = 14)
(hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k)
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 9 ∨
simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 10- Source
- Finite-frontier corollary for OP-306: the new uniform upper bound is 10 at n=13,14, and arXiv:2610.22142 Theorem 3.4 gives lower bound 9. The value 9 remains conjectural universally at these orders.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- wild_number_complete_graph_upper_sub_four_add_parityFor 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…
- 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⌋.
- 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 proof bounds the wild number of a minimum proper edge coloring of K_n between general lower and upper bounds established for complete graphs. Evaluating these bounds at n = 13 and n = 14 shows that the wild number is sandwiched between 9 and 10 in both cases, which leaves 9 and 10 as the only possible values.
The wild number of the edge coloring c is at most n - 4 + (n mod 2).
Because n = 13 or n = 14, we have n ≥ 13. Applying wild_number_complete_graph_upper_sub_four_add_parity with this inequality establishes the upper bound n - 4 + (n mod 2).
uses
wild_number_complete_graph_upper_sub_four_add_parityhave hu := wild_number_complete_graph_upper_sub_four_add_parity n k (by rcases hn with h | h <;> omega) hk c
The wild number of the edge coloring c is at least ⌊4 ⌊(n + 1) / 2⌋ / 3⌋.
Because n ≥ 13 ≥ 3, applying wild_number_complete_graph_min_proper_coloring_ge provides the lower bound ⌊4 ⌊(n + 1) / 2⌋ / 3⌋.
uses
wild_number_complete_graph_min_proper_coloring_gehave hl := wild_number_complete_graph_min_proper_coloring_ge n k (by rcases hn with h | h <;> omega) hk c
The wild number of the edge coloring c is either 9 or 10.
Splitting into the two cases n = 13 and n = 14, norm_num evaluates both bounds: for n = 13, the bounds are 9 ≤ wild number ≤ 10; for n = 14, the bounds are also 9 ≤ wild number ≤ 10. Linear integer arithmetic (omega) then concludes that the wild number must be 9 or 10 in either case.
rcases hn with rfl | rfl <;> norm_num at hu hl <;> omega
wild_number_complete_graph_upper_sub_four_add_parity- For any complete graph K_n with n ≥ 13, any minimum proper edge coloring using k colors has wild number at most n - 4 + (n mod 2).
wild_number_complete_graph_min_proper_coloring_ge- For any complete graph K_n with n ≥ 3, any minimum proper edge coloring using k colors 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
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.
theorem wild_number_complete_thirteen_fourteen_eq_nine_or_ten (n k : ℕ) (hn : n = 13 ∨ n = 14) (hk : (⊤ : SimpleGraph (Fin n)).lineGraph.chromaticNumber = k) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) : simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 9 ∨ simple_graph_wild_number (⊤ : SimpleGraph (Fin n)) c = 10 := by have hu := wild_number_complete_graph_upper_sub_four_add_parity n k (by rcases hn with h | h <;> omega) hk c have hl := wild_number_complete_graph_min_proper_coloring_ge n k (by rcases hn with h | h <;> omega) hk c rcases hn with rfl | rfl <;> norm_num at hu hl <;> omega