AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_thirteen_fourteen_eq_nine_or_ten

theoremverified

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

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.

  1. 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).

    line 6

    uses wild_number_complete_graph_upper_sub_four_add_parity

      have hu := wild_number_complete_graph_upper_sub_four_add_parity n k (by rcases hn with h | h <;> omega) hk c
  2. 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⌋.

    line 7

    uses wild_number_complete_graph_min_proper_coloring_ge

      have hl := wild_number_complete_graph_min_proper_coloring_ge n k (by rcases hn with h | h <;> omega) hk c
  3. 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.

    line 8

      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

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
See it in the graphDiscuss this resultChallenge it