wild_odd_optimal_color_connecting_partition
At 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 into floor(n/3) blocks, each of size at least three, with every used color crossing every nontrivial block cut.
Statement
theorem wild_odd_optimal_color_connecting_partition {n k : ℕ} (hn : 3 ≤ n) (hodd : n%2=1) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (W : Finset (Sym2 (Fin n))) (hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W) (hcard : W.card = n-n/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 5
- simple_graph_card_vertices_le_edges_add_componentsIn any finite simple graph, the number of vertices is at most the number of edges plus the number of connected components.
- wild_odd_color_connecting_closed_block_card_ge_threeIn a proper complete-graph edge coloring at odd order n>=3, every nonempty vertex block with no wild edge crossing its boundary has at…
- wild_block_cut_of_color_connectingA rooted vertex partition whose blocks contain both endpoints of every wild edge has an edge of every used color across every nonempty…
- 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…
- 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⌋.
- Used by 1
- 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…
The proof, explained
Consider the subgraph G spanned by the color-connecting edge set W. In an odd-order complete graph, every connected component of G is closed under edges of W and must contain at least 3 vertices, forcing the number of components to satisfy 3 c(G) ≤ n, or c(G) ≤ ⌊n/3⌋. On the other hand, the general graph bound n ≤ |E(G)| + c(G) with |E(G)| ≤ |W| = n - ⌊n/3⌋ implies c(G) ≥ ⌊n/3⌋, so G has exactly ⌊n/3⌋ components. Identifying the components with Fin (n/3) yields a rooted partition into blocks of size at least 3, and because edges in W never cross between components, the block-cut theorem guarantees that every color crosses every nontrivial block cut.
Let G be the graph on Fin n induced by the edge set W.
We enable classical reasoning and define G as the simple graph on vertex set Fin n whose edge set is determined by W.
uses
SimpleGraph.fromEdgeSetclassical let G : SimpleGraph (Fin n) := SimpleGraph.fromEdgeSet (↑W : Set (Sym2 (Fin n)))Every connected component of G has at least 3 vertices.
For any connected component C of G, its vertex set is nonempty (it contains its canonical representative `C.out`) and has no crossing edges in W: if u ∈ C, v ∉ C, and {u, v} ∈ W, then u and v are adjacent in G, which would force v ∈ C. By `wild_odd_color_connecting_closed_block_card_ge_three`, any nonempty vertex set closed under edges of W in an odd complete graph must contain at least 3 vertices.
uses
wild_odd_color_connecting_closed_block_card_ge_three,SimpleGraph.fromEdgeSet_adjhave hmin : ∀ C : G.ConnectedComponent, 3 ≤ C.supp.toFinset.card := by intro C apply wild_odd_color_connecting_closed_block_card_ge_three hn hodd c W hW C.supp.toFinset · exact ⟨C.out,Set.mem_toFinset.2 C.out_eq⟩ · intro u v huv hu hv hw have hadj : G.Adj u v := (SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩ apply hv exact Set.mem_toFinset.2 ((C.mem_supp_congr_adj hadj).1 (Set.mem_toFinset.1 hu))
The sum of component sizes is n, which implies 3 * |G.ConnectedComponent| ≤ n.
Because the connected components partition the n vertices of G, summing their sizes fiberwise yields n. Since every component has size at least 3, summing this bound over all components yields 3 * |G.ConnectedComponent| ≤ n.
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_le_sumhave hsumV : (∑ C : G.ConnectedComponent, C.supp.toFinset.card) = n := by have hi := Finset.card_eq_sum_card_fiberwise (f := G.connectedComponentMk) (s := (Finset.univ : Finset (Fin n))) (t := (Finset.univ : Finset G.ConnectedComponent)) (fun _ _ => Finset.mem_univ _) have hA : ∀ C : G.ConnectedComponent, C.supp.toFinset = Finset.univ.filter (fun v => G.connectedComponentMk v = C) := by intro C ext v simp only [Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff,Finset.mem_filter,Finset.mem_univ,true_and] simp_rw [hA] simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm have hcmin : 3 * Fintype.card G.ConnectedComponent ≤ n := by have hi := Finset.sum_le_sum (fun C (_ : C ∈ (Finset.univ : Finset G.ConnectedComponent)) => hmin C) simp only [hsumV,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_comm] at hi exact_mod_cast hi
The number of edges in G is at most |W|, and n ≤ |E(G)| + |G.ConnectedComponent|.
By definition the edges of G form a subset of W, so |E(G)| ≤ |W| = n - ⌊n/3⌋. The general graph inequality `simple_graph_card_vertices_le_edges_add_components` bounds the number of vertices by the number of edges plus the number of components. Converting the counts to `Nat.card` prepares them for linear arithmetic.
uses
Finset.card_le_card,simple_graph_card_vertices_le_edges_add_components,Nat.card_eq_fintype_cardhave hEdges : G.edgeFinset.card ≤ W.card := by apply Finset.card_le_card intro e he have he' : e ∈ G.edgeSet := SimpleGraph.mem_edgeFinset.1 he exact (SimpleGraph.edgeSet_fromEdgeSet (↑W : Set (Sym2 (Fin n))) ▸ he').1 have hcmax : n ≤ Nat.card G.edgeSet + Nat.card G.ConnectedComponent := by have hi := simple_graph_card_vertices_le_edges_add_components G simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card,Nat.card_fin] using hi have hcmin' : 3 * Nat.card G.ConnectedComponent ≤ n := by simpa only [← Nat.card_eq_fintype_card] using hcmin have hEdges' : Nat.card G.edgeSet ≤ W.card := by simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card] using hEdges
The graph G has exactly ⌊n/3⌋ connected components. automation
From 3 c(G) ≤ n we obtain c(G) ≤ ⌊n/3⌋, while n ≤ |E(G)| + c(G) ≤ n - ⌊n/3⌋ + c(G) yields c(G) ≥ ⌊n/3⌋. The integer arithmetic tactic `omega` closes the equality c(G) = ⌊n/3⌋, for both `Nat.card` and `Fintype.card`.
uses
Nat.card_eq_fintype_cardhave hcc' : Nat.card G.ConnectedComponent = n/3 := by omega have hcc : Fintype.card G.ConnectedComponent = n/3 := by simpa only [Nat.card_eq_fintype_card] using hcc'
Define the partition map p : Fin n → Fin (n/3) and root section r : Fin (n/3) → Fin n satisfying p (r t) = t.
Since G has exactly ⌊n/3⌋ connected components, we choose a bijection E between components and Fin (n/3). The partition map p assigns each vertex v to E([v]), and r(t) picks the canonical representative of component E⁻¹(t). The identity p (r t) = t follows directly by applying E to the fact that the representative belongs to E⁻¹(t).
uses
Fintype.equivFinOfCardEq,congrArglet E : G.ConnectedComponent ≃ Fin (n/3) := Fintype.equivFinOfCardEq hcc let p : Fin n → Fin (n/3) := fun v => E (G.connectedComponentMk v) let r : Fin (n/3) → Fin n := fun t => (E.symm t).out have hr : ∀ t, p (r t) = t := by intro t change E (G.connectedComponentMk ((E.symm t).out)) = t exact (congrArg E (E.symm t).out_eq).trans (E.apply_symm_apply t)
Each block p⁻¹(t) contains at least 3 vertices.
The fiber {v | p v = t} is precisely the vertex set of the component E⁻¹(t), because p v = t if and only if [v] = E⁻¹(t). Its cardinality is at least 3 by the minimum component size established earlier.
uses
SimpleGraph.ConnectedComponent.mem_supp_iffhave hpmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card := by intro t have he : ((Finset.univ : Finset (Fin n)).filter fun v => p v = t) = (E.symm t).supp.toFinset := by ext v simp only [Finset.mem_filter,Finset.mem_univ,true_and,Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff] change E (G.connectedComponentMk v) = t ↔ G.connectedComponentMk v = E.symm t exact E.apply_eq_iff_eq_symm_apply rw [he] exact hmin _
Every color crosses every nontrivial block cut, completing the existential witness.
We assemble the witnesses p and r. To show that every used color crosses every nontrivial cut S, we invoke `wild_block_cut_of_color_connecting`. Its condition requires that any edge in W connects vertices in the same block: if {u, v} ∈ W with u ≠ v, then u and v are adjacent in G, so they belong to the same component, which gives p u = p v.
uses
wild_block_cut_of_color_connecting,congrArg,SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj,SimpleGraph.fromEdgeSet_adjrefine ⟨p,r,hr,hpmin,?_⟩ apply wild_block_cut_of_color_connecting c W hW p r hr intro u v huv hw apply congrArg E exact SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj ((SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩)
SimpleGraph.fromEdgeSet- Constructs the simple graph on a given vertex type with edges given by a set of pairs, omitting self-loops.
wild_odd_color_connecting_closed_block_card_ge_three- In an odd-order (n ≥ 3) complete graph, any nonempty vertex subset closed under edges of a color-connecting set W has size at least 3.
SimpleGraph.fromEdgeSet_adj- Two distinct vertices are adjacent in `SimpleGraph.fromEdgeSet s` if and only if their pair belongs to s.
Finset.card_eq_sum_card_fiberwise- The size of a finite set equals the sum of the sizes of the fibers of any map defined on it.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set, then the sum of f over the set is at most the sum of g.
Finset.card_le_card- A subset of a finite set has cardinality at most that of the superset.
simple_graph_card_vertices_le_edges_add_components- In any finite graph, the number of vertices is at most the number of edges plus the number of connected components.
Nat.card_eq_fintype_card- For any finite type, its cardinality as a natural number (`Nat.card`) equals its `Fintype.card`.
Fintype.equivFinOfCardEq- A finite type with cardinality m is equivalent (in bijection) with Fin m.
congrArg- Applying a function to equal arguments produces equal results.
SimpleGraph.ConnectedComponent.mem_supp_iff- A vertex belongs to the support of a connected component if and only if the component is its equivalence class.
wild_block_cut_of_color_connecting- If W is a color-connecting set and every edge in W connects vertices in the same block of a rooted partition, then every color crosses every nontrivial block cut.
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj- Adjacent vertices belong to the same connected component.
- The equality showing that the number of connected components is exactly ⌊n/3⌋ is proved by the `omega` decision procedure from the bounds 3 c ≤ n and n ≤ |E| + c ≤ n - ⌊n/3⌋ + c.
- The formal proof performs technical conversions between `Fintype.card` and `Nat.card`, as well as between finsets and their set coercions.
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_odd_optimal_color_connecting_partition {n k : ℕ} (hn : 3 ≤ n) (hodd : n%2=1) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (W : Finset (Sym2 (Fin n))) (hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W) (hcard : W.card = n-n/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 classical let G : SimpleGraph (Fin n) := SimpleGraph.fromEdgeSet (↑W : Set (Sym2 (Fin n))) have hmin : ∀ C : G.ConnectedComponent, 3 ≤ C.supp.toFinset.card := by intro C apply wild_odd_color_connecting_closed_block_card_ge_three hn hodd c W hW C.supp.toFinset · exact ⟨C.out,Set.mem_toFinset.2 C.out_eq⟩ · intro u v huv hu hv hw have hadj : G.Adj u v := (SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩ apply hv exact Set.mem_toFinset.2 ((C.mem_supp_congr_adj hadj).1 (Set.mem_toFinset.1 hu)) have hsumV : (∑ C : G.ConnectedComponent, C.supp.toFinset.card) = n := by have hi := Finset.card_eq_sum_card_fiberwise (f := G.connectedComponentMk) (s := (Finset.univ : Finset (Fin n))) (t := (Finset.univ : Finset G.ConnectedComponent)) (fun _ _ => Finset.mem_univ _) have hA : ∀ C : G.ConnectedComponent, C.supp.toFinset = Finset.univ.filter (fun v => G.connectedComponentMk v = C) := by intro C ext v simp only [Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff,Finset.mem_filter,Finset.mem_univ,true_and] simp_rw [hA] simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm have hcmin : 3 * Fintype.card G.ConnectedComponent ≤ n := by have hi := Finset.sum_le_sum (fun C (_ : C ∈ (Finset.univ : Finset G.ConnectedComponent)) => hmin C) simp only [hsumV,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_comm] at hi exact_mod_cast hi have hEdges : G.edgeFinset.card ≤ W.card := by apply Finset.card_le_card intro e he have he' : e ∈ G.edgeSet := SimpleGraph.mem_edgeFinset.1 he exact (SimpleGraph.edgeSet_fromEdgeSet (↑W : Set (Sym2 (Fin n))) ▸ he').1 have hcmax : n ≤ Nat.card G.edgeSet + Nat.card G.ConnectedComponent := by have hi := simple_graph_card_vertices_le_edges_add_components G simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card,Nat.card_fin] using hi have hcmin' : 3 * Nat.card G.ConnectedComponent ≤ n := by simpa only [← Nat.card_eq_fintype_card] using hcmin have hEdges' : Nat.card G.edgeSet ≤ W.card := by simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card] using hEdges have hcc' : Nat.card G.ConnectedComponent = n/3 := by omega have hcc : Fintype.card G.ConnectedComponent = n/3 := by simpa only [Nat.card_eq_fintype_card] using hcc' let E : G.ConnectedComponent ≃ Fin (n/3) := Fintype.equivFinOfCardEq hcc let p : Fin n → Fin (n/3) := fun v => E (G.connectedComponentMk v) let r : Fin (n/3) → Fin n := fun t => (E.symm t).out have hr : ∀ t, p (r t) = t := by intro t change E (G.connectedComponentMk ((E.symm t).out)) = t exact (congrArg E (E.symm t).out_eq).trans (E.apply_symm_apply t) have hpmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card := by intro t have he : ((Finset.univ : Finset (Fin n)).filter fun v => p v = t) = (E.symm t).supp.toFinset := by ext v simp only [Finset.mem_filter,Finset.mem_univ,true_and,Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff] change E (G.connectedComponentMk v) = t ↔ G.connectedComponentMk v = E.symm t exact E.apply_eq_iff_eq_symm_apply rw [he] exact hmin _ refine ⟨p,r,hr,hpmin,?_⟩ apply wild_block_cut_of_color_connecting c W hW p r hr intro u v huv hw apply congrArg E exact SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj ((SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩)