AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_graph_formula_iff_odd_orders

theoremverified

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

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.

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

    lines 13–15

      constructor
      · intro h n k hn _ hk c
        exact h n k hn hk c
  2. 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.

    lines 16–18

      · intro h n k hn hk c
        by_cases hodd : n%2=1
        · exact h n k hn hodd hk c
  3. 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$).

    lines 19–21

    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
  4. 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.

    lines 22–25

    uses complete_graph_odd_line_graph_chromatic_number_eq

          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
  5. 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$.

    line 26

    uses wild_number_complete_even_eq_of_preceding_odd

          exact 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

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