wild_number_complete_thirteen_eq_iff_permuted_cuts
For 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 has none of the seven cuts (four blocks and three pairs of triples) closed for any color.
Statement
theorem wild_number_complete_thirteen_eq_iff_permuted_cuts
(c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 9 ↔
∃ σ : Equiv.Perm (Fin 13), ∀ (j : Fin 7) (i : Fin 13),
¬w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ)- Source
- Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- wild_complete_thirteen_partition_templateFor every partition p of thirteen vertices into four labeled blocks of size at least three, there are vertex and block-label permutations…
- 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_number_complete_odd_eq_iff_optimal_partitionFor 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…
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
- wild_complete_thirteen_one_swap_repair_obstructionThere exists a minimum proper 13-coloring of K_13, normalized so that color i misses vertex i, with this property. The fixed partition…
- 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…
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- 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⌋.
- complete_graph_odd_line_graph_chromatic_number_eqThe edge chromatic number of an odd complete graph on at least three vertices is its number of vertices.
The proof, explained
The wild number of a proper 13-edge-coloring c of K₁₃ equals 9 if and only if some permutation of the canonical 3+3+3+4 block partition has no color-closed cut among its 7 canonical cuts. In the forward direction, a wild number of 9 yields an optimal 4-block partition with parts of size at least 3, which is necessarily a permutation σ of the canonical 3+3+3+4 partition; the general theory of optimal partitions ensures that no color can leave a union of blocks closed, which rules out any closed cut among the permuted canonical cuts. In the reverse direction, pulling back the canonical partition along σ gives a 4-block partition where every non-trivial cut is a permuted canonical cut or its complement; since none is closed for any color, every color crosses every cut, yielding the upper bound ≤ 13 - 4 = 9, which matches the general lower bound ≥ 9.
The chromatic number of the line graph of K₁₃ is 13, and the equivalence splits into two directions.
Line 10 enables classical logic. Line 11 uses `complete_graph_odd_line_graph_chromatic_number_eq` to show that the line graph of K₁₃ has chromatic number 13 (since 13 is odd and 13 ≥ 3). Line 12 splits the if-and-only-if statement into the forward implication and the reverse implication.
uses
complete_graph_odd_line_graph_chromatic_number_eqclassical have hk := complete_graph_odd_line_graph_chromatic_number_eq 13 (by norm_num) (by decide) constructor
Assuming the wild number is 9, there exists an optimal 4-block partition of K₁₃, which yields a candidate vertex permutation σ.
Line 13 assumes the wild number of c is 9, and line 14 observes that 9 = 4 * ((13 + 1) / 2) / 3. Line 15 applies `wild_number_complete_odd_eq_iff_optimal_partition` to obtain an optimal partition p : Fin 13 → Fin 4 with section r, where each of the four blocks has size at least 3 (`hmin`) and every color class crosses every non-trivial cut between blocks (`hcut`). Because any partition of 13 vertices into 4 parts of size at least 3 must have part sizes 3, 3, 3, 4, line 16 applies `wild_complete_thirteen_partition_template` to obtain a permutation σ of Fin 13 and a permutation β of Fin 4 aligning p with the canonical ownership function `wsc_repair_owner`. Line 17 provides σ as the witness.
uses
wild_number_complete_odd_eq_iff_optimal_partition,wild_complete_thirteen_partition_template· intro h have heq : simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 4*((13+1)/2)/3 := by simpa using h obtain ⟨p,r,hr,hmin,hcut⟩ := (wild_number_complete_odd_eq_iff_optimal_partition (by norm_num) (by decide) hk c).1 heq obtain ⟨σ,β,hσ⟩ := wild_complete_thirteen_partition_template p hmin refine ⟨σ,?_⟩
To show σ works, assume for contradiction that some permuted canonical cut σ(C_j) is closed under color i.
Line 18 introduces an arbitrary canonical cut index j ∈ {0, …, 6}, a color i, and the hypothesis `hclosed` that the permuted cut σ(C_j) is closed under color i. Lines 19–20 invoke `w279_missing_vertex_equiv` and `wsc_color_used` to find an edge e colored with i (c(e) = i). Lines 21–24 use kernel evaluation (`decide +kernel`) to verify that each canonical cut C_j has size between 1 and 6, and is a union of canonical blocks (`hown`).
uses
w279_missing_vertex_equiv,wsc_color_usedintro j i hclosed obtain ⟨m,hm⟩ := w279_missing_vertex_equiv 13 13 (by norm_num) (by decide) hk c obtain ⟨e,he⟩ := wsc_color_used (n:=13) (by norm_num) c m hm i have hcard : ∀ j : Fin 7, 1 ≤ (wsc_repair_cuts wsc_repair_blocks j).card ∧ (wsc_repair_cuts wsc_repair_blocks j).card ≤ 6 := by decide +kernel have hown : ∀ (j : Fin 7) (u v : Fin 13), u ∈ wsc_repair_cuts wsc_repair_blocks j → wsc_repair_owner u = wsc_repair_owner v → v ∈ wsc_repair_cuts wsc_repair_blocks j := by decide +kernel
The permuted cut U = σ(C_j) is a non-empty, proper subset of vertices saturated by the fiber partition p.
Line 25 sets U = σ(C_j). Lines 26–27 use `Finset.card_image_of_injective` to show |U| = |C_j|. Lines 28–33 establish that U is non-empty and proper (U ≠ univ) since 1 ≤ |U| ≤ 6 < 13. Lines 34–39 show that U is saturated by p: if u ∈ U and p(v) = p(u), then applying β shows that σ⁻¹(v) and σ⁻¹(u) have the same canonical owner; since C_j is a union of canonical blocks, σ⁻¹(v) ∈ C_j and thus v ∈ U.
uses
Finset.card_image_of_injectivelet U := (wsc_repair_cuts wsc_repair_blocks j).image σ have hcU : U.card = (wsc_repair_cuts wsc_repair_blocks j).card := Finset.card_image_of_injective _ σ.injective have hU : U.Nonempty := Finset.card_pos.1 (by have := (hcard j).1; omega) have hproper : U ≠ Finset.univ := by intro hh have hc13 : U.card = 13 := by rw [hh]; simp have := (hcard j).2 omega have hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U := by intro u hu v hpv obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu have hvown : wsc_repair_owner (σ.symm v) = wsc_repair_owner x := by rw [← hσ (σ.symm v),σ.apply_symm_apply, hpv,hσ x] refine Finset.mem_image.2 ⟨σ.symm v, hown j x (σ.symm v) hx hvown.symm, σ.apply_symm_apply v⟩
The closure of U under color i contradicts the optimal partition property that no union of blocks is closed under an edge color.
Line 40 applies `wild_no_closed_union_of_blocks` to deduce that no non-empty proper union of blocks of the optimal partition p can be closed under the color of any edge e. Line 41 derives a contradiction since c(e) = i and U was assumed closed under color i.
uses
wild_no_closed_union_of_blockshave hncl := wild_no_closed_union_of_blocks c p hcut e U hU hproper hsat exact hncl (by simpa only [he] using hclosed)
Assuming no permuted canonical cut is closed under any color, it suffices to prove the wild number is both ≤ 9 and ≥ 9.
Line 42 introduces the permutation σ satisfying the hypothesis that no permuted cut σ(C_j) is closed under any color. Line 43 applies `le_antisymm`, reducing the problem to showing wild(c) ≤ 9 and wild(c) ≥ 9.
uses
le_antisymm· rintro ⟨σ,hσ⟩ apply le_antisymmDefine a 4-block partition p and representatives r from σ, and classify all non-trivial block subsets.
Line 44 defines p(v) = wsc_repair_owner(σ⁻¹(v)), and lines 45–46 choose representatives r(t) = σ(3t) for each block t ∈ Fin 4. Lines 47–48 verify that p(r(t)) = t using `Equiv.symm_apply_apply`. Lines 49–51 establish via `decide +kernel` that every non-empty proper subset S ⊂ Fin 4 corresponds under `wsc_repair_owner` to either one of the 7 canonical cuts C_j or its complement (`hshape`).
uses
Equiv.symm_apply_apply· let p : Fin 13 → Fin 4 := fun v => wsc_repair_owner (σ.symm v) let r0 (t : Fin 4) : Fin 13 := ⟨3*t.val,by have := t.isLt; omega⟩ let r : Fin 4 → Fin 13 := fun t => σ (r0 t) have hroot : ∀ t, wsc_repair_owner (r0 t) = t := by decide +kernel have hr : ∀ t, p (r t) = t := by intro t; simpa only [p,r,Equiv.symm_apply_apply] using hroot t have hshape : ∀ S : Finset (Fin 4), S.Nonempty → S ≠ Finset.univ → ∃ j : Fin 7, (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∈ wsc_repair_cuts wsc_repair_blocks j) ∨ (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∉ wsc_repair_cuts wsc_repair_blocks j) := by decide +kernel
Every edge color crosses every non-trivial cut between blocks of p.
Lines 52–56 suppose for contradiction that for some edge e and non-empty proper S ⊂ Fin 4, no edge of color c(e) crosses between p⁻¹(S) and p⁻¹(Sᶜ). Line 57 splits on `hshape`. In the first case (lines 58–67), p⁻¹(S) = σ(C_j), so the absence of crossing edges of color c(e) means σ(C_j) is closed under c(e), contradicting the hypothesis hσ. In the second case (lines 68–80), p⁻¹(Sᶜ) = σ(C_j), which similarly implies σ(C_j) is closed under c(e) using edge color symmetry `w279_c_swap`, again contradicting hσ.
uses
Equiv.symm_apply_apply,wild_kn_mem,w279_c_swaphave hcut : ∀ (e : (⊤ : SimpleGraph (Fin 13)).edgeSet) (S : Finset (Fin 4)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin 13) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by intro e S hS hproper by_contra! hno obtain ⟨j,hj | hj⟩ := hshape S hS hproper · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu by_contra hv have hxS : p (σ x) ∈ S := by simpa only [p,Equiv.symm_apply_apply] using (hj x).2 hx have hvS : p v ∉ S := by intro hh have hvD := (hj (σ.symm v)).1 hh exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩) exact hno (σ x) v huv hxS hvS hc · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu by_contra hv have hxS : p (σ x) ∉ S := by intro hh have hh' : wsc_repair_owner x ∈ S := by simpa only [p,Equiv.symm_apply_apply] using hh exact (hj x).1 hh' hx have hvS : p v ∈ S := by apply (hj (σ.symm v)).2 intro hvD exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩) exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c (Ne.symm huv)).trans hc)
The wild number of c is at most 9.
Line 81 applies `simple_graph_wild_number_le_of_block_cut_condition` with n = 13 and q = 4, which yields wild(c) ≤ 13 - 4 = 9 because p and r satisfy the cut-crossing condition. Lines 82–83 compute 13 - 4 = 9 with `norm_num` and finish the upper bound.
uses
simple_graph_wild_number_le_of_block_cut_conditionhave hu := simple_graph_wild_number_le_of_block_cut_condition (n:=13) (q:=4) (by norm_num) c p r hr hcut norm_num at hu exact hu
The wild number of c is at least 9, concluding that it equals 9.
Line 84 applies `wild_number_complete_graph_min_proper_coloring_ge`, which provides the general lower bound 4 * ((13 + 1) / 2) / 3 ≤ wild(c) for any proper 13-coloring of K₁₃. Lines 85–86 evaluate this lower bound to 9 via `norm_num` and close the goal.
uses
wild_number_complete_graph_min_proper_coloring_ge· have hl := wild_number_complete_graph_min_proper_coloring_ge 13 13 (by norm_num) hk c norm_num at hl exact hl
complete_graph_odd_line_graph_chromatic_number_eq- For any odd n ≥ 3, the chromatic number of the line graph of the complete graph K_n is equal to n.
wild_number_complete_odd_eq_iff_optimal_partition- For an odd complete graph K_n (n ≥ 3) properly edge-colored with k = χ(L(K_n)) colors, the wild number equals 4⌊(n+1)/2⌋/3 if and only if there exists a vertex partition into ⌊n/3⌋ blocks, each of size at least 3, such that every color class crosses every non-trivial cut between blocks.
wild_complete_thirteen_partition_template- Any partition of a 13-element set into 4 blocks of size at least 3 is isomorphic to the canonical 3+3+3+4 partition via a permutation of the 13 vertices and a permutation of the 4 block labels.
w279_missing_vertex_equiv- In any proper k-edge-coloring of an odd complete graph K_n with k = χ(L(K_n)), each color class misses exactly one vertex, inducing a bijection between the colors and the vertices.
wsc_color_used- In a proper edge-coloring of K_n (n ≥ 3) with a missing-vertex bijection, every color appears on at least one edge.
Finset.card_image_of_injective- An injective function preserves the cardinality of a finite set under image.
wild_no_closed_union_of_blocks- If an edge-coloring satisfies the cut condition for a block partition p, then no non-empty proper union of blocks can be closed under the color of any edge.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Equiv.symm_apply_apply- Applying an equivalence to the image of an element under its inverse yields the original element: e(e⁻¹(x)) = x.
wild_kn_mem- An unordered pair of distinct vertices in a complete graph forms an edge of the complete graph.
w279_c_swap- The color assigned to an undirected edge {u, v} is symmetric in its endpoints: c({u, v}) = c({v, u}).
simple_graph_wild_number_le_of_block_cut_condition- If a coloring of K_n admits a partition into q blocks with representatives such that every color crosses every non-trivial cut between blocks, then the wild number of the coloring is at most n - q.
wild_number_complete_graph_min_proper_coloring_ge- For any proper edge-coloring of K_n with chromatic number k, the wild number is bounded below by 4⌊(n+1)/2⌋/3.
- The 7 canonical cuts (wsc_repair_cuts wsc_repair_blocks) consist of the 4 individual blocks of sizes 3, 3, 3, 4 and the 3 pairs of size-3 blocks. Together with their complements, they account for all 14 non-trivial cuts of the 4 blocks.
- Several combinatorial properties of the canonical cuts (their sizes between 1 and 6, their invariance under block ownership, and the classification of all 14 non-trivial subsets of Fin 4) are verified by the Lean kernel via `decide +kernel`.
- Arithmetic reductions such as 4 * ((13 + 1) / 2) / 3 = 9 and 13 - 4 = 9 are discharged automatically by `norm_num`.
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_thirteen_eq_iff_permuted_cuts (c : (⊤ : SimpleGraph (Fin 13)).lineGraph.Coloring (Fin 13)) : simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 9 ↔ ∃ σ : Equiv.Perm (Fin 13), ∀ (j : Fin 7) (i : Fin 13), ¬w279_closed c i ((wsc_repair_cuts wsc_repair_blocks j).image σ) := by classical have hk := complete_graph_odd_line_graph_chromatic_number_eq 13 (by norm_num) (by decide) constructor · intro h have heq : simple_graph_wild_number (⊤ : SimpleGraph (Fin 13)) c = 4*((13+1)/2)/3 := by simpa using h obtain ⟨p,r,hr,hmin,hcut⟩ := (wild_number_complete_odd_eq_iff_optimal_partition (by norm_num) (by decide) hk c).1 heq obtain ⟨σ,β,hσ⟩ := wild_complete_thirteen_partition_template p hmin refine ⟨σ,?_⟩ intro j i hclosed obtain ⟨m,hm⟩ := w279_missing_vertex_equiv 13 13 (by norm_num) (by decide) hk c obtain ⟨e,he⟩ := wsc_color_used (n:=13) (by norm_num) c m hm i have hcard : ∀ j : Fin 7, 1 ≤ (wsc_repair_cuts wsc_repair_blocks j).card ∧ (wsc_repair_cuts wsc_repair_blocks j).card ≤ 6 := by decide +kernel have hown : ∀ (j : Fin 7) (u v : Fin 13), u ∈ wsc_repair_cuts wsc_repair_blocks j → wsc_repair_owner u = wsc_repair_owner v → v ∈ wsc_repair_cuts wsc_repair_blocks j := by decide +kernel let U := (wsc_repair_cuts wsc_repair_blocks j).image σ have hcU : U.card = (wsc_repair_cuts wsc_repair_blocks j).card := Finset.card_image_of_injective _ σ.injective have hU : U.Nonempty := Finset.card_pos.1 (by have := (hcard j).1; omega) have hproper : U ≠ Finset.univ := by intro hh have hc13 : U.card = 13 := by rw [hh]; simp have := (hcard j).2 omega have hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U := by intro u hu v hpv obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu have hvown : wsc_repair_owner (σ.symm v) = wsc_repair_owner x := by rw [← hσ (σ.symm v),σ.apply_symm_apply, hpv,hσ x] refine Finset.mem_image.2 ⟨σ.symm v, hown j x (σ.symm v) hx hvown.symm, σ.apply_symm_apply v⟩ have hncl := wild_no_closed_union_of_blocks c p hcut e U hU hproper hsat exact hncl (by simpa only [he] using hclosed) · rintro ⟨σ,hσ⟩ apply le_antisymm · let p : Fin 13 → Fin 4 := fun v => wsc_repair_owner (σ.symm v) let r0 (t : Fin 4) : Fin 13 := ⟨3*t.val,by have := t.isLt; omega⟩ let r : Fin 4 → Fin 13 := fun t => σ (r0 t) have hroot : ∀ t, wsc_repair_owner (r0 t) = t := by decide +kernel have hr : ∀ t, p (r t) = t := by intro t; simpa only [p,r,Equiv.symm_apply_apply] using hroot t have hshape : ∀ S : Finset (Fin 4), S.Nonempty → S ≠ Finset.univ → ∃ j : Fin 7, (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∈ wsc_repair_cuts wsc_repair_blocks j) ∨ (∀ v : Fin 13, wsc_repair_owner v ∈ S ↔ v ∉ wsc_repair_cuts wsc_repair_blocks j) := by decide +kernel have hcut : ∀ (e : (⊤ : SimpleGraph (Fin 13)).edgeSet) (S : Finset (Fin 4)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin 13) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by intro e S hS hproper by_contra! hno obtain ⟨j,hj | hj⟩ := hshape S hS hproper · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu by_contra hv have hxS : p (σ x) ∈ S := by simpa only [p,Equiv.symm_apply_apply] using (hj x).2 hx have hvS : p v ∉ S := by intro hh have hvD := (hj (σ.symm v)).1 hh exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩) exact hno (σ x) v huv hxS hvS hc · apply hσ j (c e) intro u hu v huv hc obtain ⟨x,hx,rfl⟩ := Finset.mem_image.1 hu by_contra hv have hxS : p (σ x) ∉ S := by intro hh have hh' : wsc_repair_owner x ∈ S := by simpa only [p,Equiv.symm_apply_apply] using hh exact (hj x).1 hh' hx have hvS : p v ∈ S := by apply (hj (σ.symm v)).2 intro hvD exact hv (Finset.mem_image.2 ⟨σ.symm v,hvD,σ.apply_symm_apply v⟩) exact hno v (σ x) (Ne.symm huv) hvS hxS ((w279_c_swap c (Ne.symm huv)).trans hc) have hu := simple_graph_wild_number_le_of_block_cut_condition (n:=13) (q:=4) (by norm_num) c p r hr hcut norm_num at hu exact hu · have hl := wild_number_complete_graph_min_proper_coloring_ge 13 13 (by norm_num) hk c norm_num at hl exact hl