AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_graph_large_odd_multiple_three_eq

theoremverifiedoriginal

For every odd integer q>=100001, every natural number k equal to the chromatic number of the line graph of the complete graph K_(3q), and every proper edge coloring c of K_(3q) with colors Fin k, the wild number equals 2q. Equivalently, the conjectured equality holds for every n>=300003 with n congruent to 3 modulo 6, for every minimum proper edge coloring.

Statement

theorem wild_number_complete_graph_large_odd_multiple_three_eq (q k : ℕ)
    (hq : 100001 ≤ q) (hodd : q % 2 = 1)
    (hk : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.chromaticNumber = k)
    (c : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.Coloring (Fin k)) :
    simple_graph_wild_number (⊤ : SimpleGraph (Fin (3 * q))) c = 2 * q
Related work
arXiv:2610.22142, Section 6 conjecture and Theorems 3.4 and 3.5 (the paper proves equality for 3<=n<=12); existing AFTD case n=279. Uniform permutation-event argument with elementary binomial bounds extends equality to an infinite family. Literature checked 2026-10-28 at https://arxiv.org/abs/2610.22142 and searches for the paper title, wild number minimum proper coloring, and wild number 279.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Read back from the Lean

For any natural numbers $q$ and $k$ such that $q \ge 100001$ and $q$ is odd ($q \bmod 2 = 1$), if $k$ is the chromatic number of the line graph of the complete graph on $\mathrm{Fin}(3q)$ (that is, the chromatic index of $K_{3q}$), then for every proper coloring $c$ of the line graph of the complete graph on $\mathrm{Fin}(3q)$ using $k$ colors (i.e., every proper edge-coloring of $K_{3q}$ with $k$ colors), the wild number of the complete graph on $\mathrm{Fin}(3q)$ with respect to $c$ is equal to $2q$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem proves that the wild number of any minimum proper edge coloring of the complete graph $K_{3q}$ equals $2q$, for every odd integer $q \ge 100001$. The argument proceeds by establishing matching upper and lower bounds. A general complete-graph lower bound gives $\mathrm{wild\_number} \ge \lfloor \frac{4}{3} \lfloor \frac{3q+1}{2} \rfloor \rfloor = 2q$ via integer arithmetic for odd $q$. For the upper bound, every color class in a minimum edge coloring leaves exactly one vertex uncovered, inducing a bijection between colors and vertices, and an analytic mass criterion on triple partitions bounds the wild number from above by $2q$.

  1. Each color in the edge coloring is omitted at exactly one vertex, providing an equivalence $m : \mathrm{Fin}(k) \simeq \mathrm{Fin}(3q)$.

    Since $q \ge 100001$ is odd, the complete graph $K_{3q}$ has odd order $3q \ge 3$, which is checked by linear arithmetic (`omega`). Lemma `w279_missing_vertex_equiv` applies to any minimum proper edge coloring $c$ of $K_{3q}$, yielding an equivalence $m$ between color indices $\mathrm{Fin}(k)$ and vertices $\mathrm{Fin}(3q)$ such that vertex $v$ misses color $i$ if and only if $v = m(i)$.

    line 6

    uses w279_missing_vertex_equiv

      obtain ⟨m, hm⟩ := w279_missing_vertex_equiv (3 * q) k (by omega) (by omega) hk c
  2. The number of colors $k$ equals $3q$.

    Because $m$ is an equivalence between $\mathrm{Fin}(k)$ and $\mathrm{Fin}(3q)$, their cardinalities must coincide by `Fintype.card_congr`, establishing $k = 3q$. Substituting $k = 3q$ replaces $k$ with $3q$ throughout the context.

    lines 7–8

    uses Fintype.card_congr

      have hk' : k = 3 * q := by simpa using Fintype.card_congr m
      subst k
  3. The wild number of $c$ on $K_{3q}$ is at most $2q$.

    Since $q \ge 100001$ is odd, lemma `wild_triple_partition_large_order_mass_bound` ensures that both the pair and vertex mass sums for triple partitions are at most $1/50$. Because $q \ge 3$ (verified by `omega`) and $q$ is odd, lemma `wild_triple_partition_mass_criterion` applies to the coloring $c$ and the missing-vertex bijection $m$, establishing the upper bound $\mathrm{wild\_number}(K_{3q}, c) \le 2q$.

    lines 9–10

    uses wild_triple_partition_large_order_mass_bound, wild_triple_partition_mass_criterion

      obtain ⟨hp, hv⟩ := wild_triple_partition_large_order_mass_bound q hq hodd
      have hu := wild_triple_partition_mass_criterion (by omega : 3 ≤ q) hodd hp hv c m hm
  4. The wild number of $c$ on $K_{3q}$ is at least $2q$.

    Lemma `wild_number_complete_graph_min_proper_coloring_ge` establishes a general lower bound $\lfloor \frac{4}{3} \lfloor \frac{n+1}{2} \rfloor \rfloor \le \mathrm{wild\_number}$ for any minimum proper edge coloring of $K_n$ ($n \ge 3$). For $n = 3q$ with $q$ odd, integer division arithmetic (`omega`) simplifies $\lfloor \frac{4}{3} \lfloor \frac{3q+1}{2} \rfloor \rfloor$ to $2q$. Rewriting with this equality yields $2q \le \mathrm{wild\_number}(K_{3q}, c)$.

    lines 11–13

    uses wild_number_complete_graph_min_proper_coloring_ge

      have hl := wild_number_complete_graph_min_proper_coloring_ge (3 * q) (3 * q) (by omega) hk c
      have he : 4 * ((3 * q + 1) / 2) / 3 = 2 * q := by omega
      rw [he] at hl
  5. The wild number of $c$ on $K_{3q}$ is equal to $2q$.

    Combining the upper bound $\mathrm{wild\_number}(K_{3q}, c) \le 2q$ and the lower bound $2q \le \mathrm{wild\_number}(K_{3q}, c)$ by antisymmetry of the ordering (`le_antisymm`) completes the proof.

    line 14

    uses le_antisymm

      exact le_antisymm hu hl
w279_missing_vertex_equiv
In any minimum proper edge coloring of an odd complete graph $K_n$ ($n \ge 3$) with $k$ colors, each color is omitted at exactly one vertex, yielding an equivalence between the color set $\mathrm{Fin}(k)$ and the vertex set $\mathrm{Fin}(n)$.
Fintype.card_congr
An equivalence between two finite types implies that they have the same cardinality.
wild_triple_partition_large_order_mass_bound
For any odd integer $q \ge 100001$, both the pair mass sum and the vertex mass sum for triple partitions are at most $1/50$.
wild_triple_partition_mass_criterion
For an odd order parameter $q \ge 3$, if both the pair and vertex mass bounds are at most $1/50$ and the edge coloring satisfies the missing-vertex equivalence, then the wild number of $K_{3q}$ under this coloring is at most $2q$.
wild_number_complete_graph_min_proper_coloring_ge
For any complete graph $K_n$ ($n \ge 3$) and any minimum proper edge coloring with $k$ colors, the wild number is bounded below by $\lfloor \frac{4}{3} \lfloor \frac{n+1}{2} \rfloor \rfloor$.
le_antisymm
In any partially ordered type, if $a \le b$ and $b \le a$, then $a = b$.

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_graph_large_odd_multiple_three_eq (q k : ℕ)    (hq : 100001 ≤ q) (hodd : q % 2 = 1)    (hk : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.chromaticNumber = k)    (c : (⊤ : SimpleGraph (Fin (3 * q))).lineGraph.Coloring (Fin k)) :    simple_graph_wild_number (⊤ : SimpleGraph (Fin (3 * q))) c = 2 * q := by  obtain ⟨m, hm⟩ := w279_missing_vertex_equiv (3 * q) k (by omega) (by omega) hk c  have hk' : k = 3 * q := by simpa using Fintype.card_congr m  subst k  obtain ⟨hp, hv⟩ := wild_triple_partition_large_order_mass_bound q hq hodd  have hu := wild_triple_partition_mass_criterion (by omega : 3 ≤ q) hodd hp hv c m hm  have hl := wild_number_complete_graph_min_proper_coloring_ge (3 * q) (3 * q) (by omega) hk c  have he : 4 * ((3 * q + 1) / 2) / 3 = 2 * q := by omega  rw [he] at hl  exact le_antisymm hu hl
See it in the graphDiscuss this resultChallenge it