AFTD Auto-Formalizing Theoretical Domains

wild_number_complete_odd_eq_iff_optimal_partition

theoremverified

For every minimum proper coloring of K_n at odd order n>=3, its wild number equals floor(4*ceil(n/2)/3) if and only if there is a rooted partition into floor(n/3) blocks of at least three vertices such that every used color crosses every nonempty proper block cut.

Statement

theorem wild_number_complete_odd_eq_iff_optimal_partition {n k : ℕ} (hn : 3 ≤ n) (hodd : n%2=1)
    (hk : (⊤ : 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 ↔
    ∃ (p : Fin n → Fin (n/3)) (r : Fin (n/3) → Fin n),
      (∀ t, p (r t) = t) ∧
      (∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card) ∧
      (∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin (n/3))),
        S.Nonempty → S ≠ Finset.univ →
        ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e)
Source
Structural necessity and certificate-soundness helpers for the OP-306 campaign; arXiv:2610.22142, Sections 3.3.1 and 3.3.2. These make the optimal block-partition route an equivalence at every odd order; no new exact wild-number case or bound is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 5

The proof, explained

The theorem characterizes when the wild number of a minimum proper edge-coloring of an odd complete graph $K_n$ ($n \ge 3$) attains its theoretical lower bound $4 \lfloor (n + 1) / 2 \rfloor / 3 = n - \lfloor n / 3 \rfloor$. In the forward direction, an optimal color-connecting edge set achieving the wild number has size $n - \lfloor n / 3 \rfloor$, which by a structural theorem (`wild_odd_optimal_color_connecting_partition`) induces the required partition into $\lfloor n / 3 \rfloor$ blocks of size at least 3 where every color crosses every cut. In the reverse direction, such a block partition provides the matching upper bound via `simple_graph_wild_number_le_of_block_cut_condition`, while the general lower bound for complete graphs (`wild_number_complete_graph_min_proper_coloring_ge`) forces equality.

  1. The arithmetic identity $4 \lfloor (n + 1) / 2 \rfloor / 3 = n - \lfloor n / 3 \rfloor$ holds for every odd integer $n \ge 3$.

    Because $n$ is odd, integer division $(n + 1) / 2$ evaluates to $\lceil n / 2 \rceil$. A case analysis modulo 6 shows that $\lfloor 4 \lceil n / 2 \rceil / 3 \rfloor = n - \lfloor n / 3 \rfloor$. The `omega` tactic proves this Presburger arithmetic equality automatically.

    line 15

      have he : 4*((n+1)/2)/3 = n-n/3 := by omega
  2. If the wild number equals $4 \lfloor (n + 1) / 2 \rfloor / 3$, then there exists the desired rooted block partition.

    Assume the wild number equals $4 \lfloor (n + 1) / 2 \rfloor / 3$. Since $n \ge 3$, the complete graph $K_n$ has a nonempty vertex set and is connected by `SimpleGraph.connected_top`. By `simple_graph_wild_number_attained`, there is a color-connecting edge set $W$ of cardinality equal to the wild number, which by the arithmetic identity equals $n - \lfloor n / 3 \rfloor$. Applying `wild_odd_optimal_color_connecting_partition` directly yields the desired rooted partition into $\lfloor n / 3 \rfloor$ blocks of size at least 3 whose cuts are all crossed by every color.

    lines 16–21

    uses SimpleGraph.connected_top, simple_graph_wild_number_attained, wild_odd_optimal_color_connecting_partition

      constructor
      · intro h
        letI : Nonempty (Fin n) := ⟨⟨0,by omega⟩⟩
        obtain ⟨W,hcard,hW⟩ := simple_graph_wild_number_attained (⊤ : SimpleGraph (Fin n)) c SimpleGraph.connected_top
        apply wild_odd_optimal_color_connecting_partition hn hodd c W hW
        rw [hcard,h,he]
  3. Conversely, if such a rooted block partition exists, the wild number equals $4 \lfloor (n + 1) / 2 \rfloor / 3$.

    Assume there exists a rooted partition into $\lfloor n / 3 \rfloor$ blocks such that every color crosses every nontrivial block cut. By antisymmetry (`le_antisymm`), it suffices to establish both inequalities. For the upper bound, rewriting the bound via the arithmetic identity to $n - \lfloor n / 3 \rfloor$ allows `simple_graph_wild_number_le_of_block_cut_condition` to show that the wild number is at most $n - \lfloor n / 3 \rfloor$. For the lower bound, `wild_number_complete_graph_min_proper_coloring_ge` states that any minimum proper coloring of an odd complete graph $K_n$ ($n \ge 3$) has wild number at least $4 \lfloor (n + 1) / 2 \rfloor / 3$, completing the equality.

    lines 22–26

    uses le_antisymm, simple_graph_wild_number_le_of_block_cut_condition, wild_number_complete_graph_min_proper_coloring_ge

      · rintro ⟨p,r,hr,hmin,hcut⟩
        apply le_antisymm
        · rw [he]
          exact simple_graph_wild_number_le_of_block_cut_condition (by omega) c p r hr hcut
        · exact wild_number_complete_graph_min_proper_coloring_ge n k hn hk c
le_antisymm
In a partial order, if $a \le b$ and $b \le a$, then $a = b$.
SimpleGraph.connected_top
The complete graph on any nonempty vertex type is connected.
simple_graph_wild_number_attained
For any connected graph with an edge-coloring, the wild number is attained by some color-connecting edge set of minimum cardinality.
simple_graph_wild_number_le_of_block_cut_condition
If an edge-colored complete graph on $n$ vertices admits a rooted partition into $q$ blocks such that every edge color crosses every nontrivial block cut, then its wild number is at most $n - q$.
wild_number_complete_graph_min_proper_coloring_ge
For any minimum proper edge-coloring of an odd complete graph $K_n$ ($n \ge 3$), the wild number is at least $4 \lfloor (n + 1) / 2 \rfloor / 3$.
wild_odd_optimal_color_connecting_partition
For an odd complete graph $K_n$ ($n \ge 3$) with a minimum proper edge-coloring, any color-connecting edge set of optimal size $n - \lfloor n / 3 \rfloor$ induces a rooted partition into $\lfloor n / 3 \rfloor$ blocks of size at least 3 such that every used color crosses every proper nonempty block cut.

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 BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem wild_number_complete_odd_eq_iff_optimal_partition {n k : ℕ} (hn : 3 ≤ n) (hodd : n%2=1)    (hk : (⊤ : 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 ↔    ∃ (p : Fin n → Fin (n/3)) (r : Fin (n/3) → Fin n),      (∀ t, p (r t) = t) ∧      (∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card) ∧      (∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin (n/3))),        S.Nonempty → S ≠ Finset.univ →        ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e) := by  have he : 4*((n+1)/2)/3 = n-n/3 := by omega  constructor  · intro h    letI : Nonempty (Fin n) := ⟨⟨0,by omega⟩⟩    obtain ⟨W,hcard,hW⟩ := simple_graph_wild_number_attained (⊤ : SimpleGraph (Fin n)) c SimpleGraph.connected_top    apply wild_odd_optimal_color_connecting_partition hn hodd c W hW    rw [hcard,h,he]  · rintro ⟨p,r,hr,hmin,hcut⟩    apply le_antisymm    · rw [he]      exact simple_graph_wild_number_le_of_block_cut_condition (by omega) c p r hr hcut    · exact wild_number_complete_graph_min_proper_coloring_ge n k hn hk c
See it in the graphDiscuss this resultChallenge it