wild_number_complete_odd_eq_iff_optimal_partition
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
- wild_odd_optimal_color_connecting_partitionAt odd order n>=3, every color-connecting edge set of size n-floor(n/3) in a proper complete-graph edge coloring yields a rooted partition…
- simple_graph_wild_number_attainedFor any finite connected edge-colored graph, some finite color-connecting edge set has cardinality exactly its wild number.
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
- 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_is_color_connectingLet γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning…
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- Used by 5
- wild_number_complete_thirteen_eq_iff_permuted_cutsFor every proper 13-coloring of K_13, its wild number is nine if and only if some permutation of the canonical 3+3+3+4 vertex partition…
- wild_odd_sharpness_of_weighted_cubic_costAt any positive odd complete-graph order n>=3, for any minimum proper coloring and any finite family of rooted floor(n/3)-block partitions…
- wild_no_closed_union_of_blocksIf every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of…
- wild_odd_sharpness_of_adaptive_cubic_momentsFor any minimum proper coloring at odd order n>=3 and any finite family of rooted partitions into floor(n/3) blocks of size at least…
- wild_number_complete_even_eq_of_preceding_oddFor odd n>=3, if every proper n-coloring of K_n has the conjectured sharp wild number, then every minimum proper coloring of K_(n+1) has…
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.
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.
have he : 4*((n+1)/2)/3 = n-n/3 := by omega
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.
uses
SimpleGraph.connected_top,simple_graph_wild_number_attained,wild_odd_optimal_color_connecting_partitionconstructor · 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]
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.
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.
- In Lean, integer division `/` truncates towards zero. For odd $n$, $(n + 1) / 2 = \lceil n / 2 \rceil$, so `4 * ((n + 1) / 2) / 3` represents $\lfloor 4 \lceil n / 2 \rceil / 3 \rfloor$, which equals $n - \lfloor n / 3 \rfloor$.
- The block-size lower bound of at least 3 (`hmin`) is required only in the forward direction; in the reverse direction, the cut-crossing condition alone suffices to upper bound the wild number.
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.
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