complete_graph_odd_rainbow_matching_third_bound
Every proper edge coloring of an odd complete graph of order n>=3 has a matching with pairwise distinct colors and at least ceil(n/3) edges.
Statement
theorem complete_graph_odd_rainbow_matching_third_bound {n k : ℕ} (hn : 3 ≤ n) (hodd : n % 2 = 1) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) : ∃ W : Finset (⊤ : SimpleGraph (Fin n)).edgeSet, (∀ a ∈ W, ∀ b ∈ W, a ≠ b → Disjoint a.val.toFinset b.val.toFinset) ∧ Set.InjOn (fun e => c e) (↑W : Set (⊤ : SimpleGraph (Fin n)).edgeSet) ∧ n ≤ 3 * W.card
- Source
- OP-306 / IN-338 general construction helpers related to arXiv:2610.22142, Sections3.3.2 and6. Binary leaf-translation classification and standard maximal rainbow-matching counting, used to repair the diagnosed sampling law (experiments8414 and8442). No new exact wild-number case, numerical bound or research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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.
- 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⌋.
The proof, explained
We choose a rainbow matching W of maximal cardinality in the complete graph K_n, letting V be the 2|W| vertices covered by W, U the remaining unsaturated vertices, and C the |W| colors on W. Maximality of W implies that every edge with both endpoints in U must receive a color in C, properly edge-coloring the induced complete graph on U with colors from C. Since n is odd and |V| = 2|W| is even, |U| is odd; when |U| ≥ 3, the chromatic index of K_{|U|} is |U|, forcing |U| ≤ |C| = |W|, which also holds when |U| = 1. Therefore n = |U| + 2|W| ≤ 3|W|, giving |W| ≥ ⌈n/3⌉.
The line graph of K_{|U|} is |C|-colorable.
We identify the vertex subset U with Fin(|U|) via a bijection E, which induces an embedding of the complete graph K_{|U|} into K_n. Pulling back the edge coloring c of K_n yields an edge coloring cc of K_{|U|}. By assumption, every edge with both endpoints in U receives a color in C, so the values of cc lie in C. Restricting cc to the subtype C and relabeling colors through the equivalence C ≃ Fin(|C|) produces a valid proper coloring of the line graph of K_{|U|} using |C| colors.
uses
Fintype.equivOfCardEq,Subtype.ext,Sym2.inductionOn,SimpleGraph.Coloring.mk,congrArg,SimpleGraph.recolorOfEquiv,Fintype.equivFin,Fintype.card_coeclassical let E : Fin U.card ≃ ↥U := Fintype.equivOfCardEq (by simp) let f : Fin U.card ↪ Fin n := ⟨fun v => (E v).val, fun a b h => E.injective (Subtype.ext h)⟩ let cc := c.comap (SimpleGraph.Embedding.completeGraph f).toCopy.toLineGraphEmbedding.toHom have hcc : ∀ e : (⊤ : SimpleGraph (Fin U.card)).edgeSet, cc e ∈ C := by rintro ⟨e, he⟩ induction e using Sym2.inductionOn with | hf a b => have hab : a ≠ b := by simpa using he change c ⟨s(f a,f b),_⟩ ∈ C exact hcol (f a) (E a).property (f b) (E b).property (fun h => hab (f.injective h)) let cs : (⊤ : SimpleGraph (Fin U.card)).lineGraph.Coloring ↥C := SimpleGraph.Coloring.mk (fun e => ⟨cc e, hcc e⟩) (by intro a b hab heq exact (cc.valid hab) (congrArg Subtype.val heq)) have hcfin : (⊤ : SimpleGraph (Fin U.card)).lineGraph.Colorable C.card := by let cf := (SimpleGraph.recolorOfEquiv _ (Fintype.equivFin ↥C)) cs have : (⊤ : SimpleGraph (Fin U.card)).lineGraph.Colorable (Fintype.card ↥C) := ⟨cf⟩ simpa only [Fintype.card_coe] using this
|U| ≤ |C|.
Because the line graph of K_{|U|} is |C|-colorable, its chromatic number is at most |C|. By complete_graph_odd_line_graph_chromatic_number_eq, for odd |U| ≥ 3, the chromatic number of the line graph of K_{|U|} is exactly |U|. Hence |U| ≤ |C|.
uses
complete_graph_odd_line_graph_chromatic_number_eqhave hh := hcfin.chromaticNumber_le rw [complete_graph_odd_line_graph_chromatic_number_eq U.card hU hodd] at hh exact_mod_cast hh
There exists a rainbow matching W in K_n of maximal size.
We define a rainbow matching to be a set of edges that are pairwise vertex-disjoint and receive pairwise distinct colors under c. The family Q of all rainbow matchings is nonempty (containing the empty matching) and finite, so we can pick an element W in Q that maximizes |W|.
classical let E := (⊤ : SimpleGraph (Fin n)).edgeSet let P : Finset E → Prop := fun W => (∀ a ∈ W, ∀ b ∈ W, a ≠ b → Disjoint a.val.toFinset b.val.toFinset) ∧ Set.InjOn (fun e => c e) (↑W : Set E) let Q : Finset (Finset E) := univ.filter P have hQ : Q.Nonempty := ⟨∅, by simp [Q, P, Set.InjOn]⟩ obtain ⟨W, hWQ, hmax⟩ := Q.exists_max_image card hQ have hW : P W := (mem_filter.mp hWQ).2
The vertices partition into the 2|W| vertices V covered by W and the unsaturated vertices U, with |U| + 2|W| = n, and |C| = |W| where C is the set of colors on W.
Let V be the union of the endpoints of edges in W, U = V(K_n) \ V the unsaturated vertices, and C the set of colors appearing on W. Since W is a matching of 2-element edges, card_biUnion gives |V| = 2|W|. Since W is rainbow, c is injective on W, so card_image_of_injOn gives |C| = |W|. Finally, |U| + |V| = n because U is the complement of V in the n-element vertex set.
uses
card_biUnion,Sym2.card_toFinset_of_not_isDiag,sum_congr,sum_const,nsmul_eq_mul,Nat.mul_comm,card_image_of_injOn,card_sdiff_add_card_eq_card,subset_univ,card_univ,Fintype.card_finlet V : Finset (Fin n) := W.biUnion fun e => e.val.toFinset let U : Finset (Fin n) := univ \ V let C : Finset (Fin k) := W.image fun e => c e have hV : V.card = 2 * W.card := by dsimp only [V] rw [card_biUnion (by intro a ha b hb hab; exact hW.1 a ha b hb hab)] have htwo : ∀ e ∈ W, e.val.toFinset.card = 2 := by intro e _ exact Sym2.card_toFinset_of_not_isDiag e.val ((⊤ : SimpleGraph (Fin n)).not_isDiag_of_mem_edgeSet e.property) rw [sum_congr rfl htwo, sum_const, nsmul_eq_mul] simp only [Nat.cast_id, Nat.mul_comm] have hC : C.card = W.card := card_image_of_injOn hW.2 have hUV : U.card + V.card = n := by have hh := card_sdiff_add_card_eq_card (subset_univ V) simpa only [card_univ, Fintype.card_fin] using hh
Every edge with both endpoints in U has its color in C.
Suppose for contradiction that there exist distinct vertices u, v ∈ U whose connecting edge e = {u, v} has color c(e) ∉ C. Since u and v are outside V, e is vertex-disjoint from all edges in W. Furthermore, because c(e) ∉ C = c(W) and W is rainbow, W ∪ {e} is also a rainbow matching. Since e ∉ W, the augmented matching has size |W| + 1, contradicting the maximality of W.
uses
wild_kn_mem,mem_univ,card_insert_of_notMemhave hcol : ∀ u ∈ U, ∀ v ∈ U, ∀ h : u ≠ v, c ⟨s(u,v),wild_kn_mem h⟩ ∈ C := by intro u hu v hv huv by_contra hno let e : E := ⟨s(u,v),wild_kn_mem huv⟩ have huV : u ∉ V := (mem_sdiff.mp hu).2 have hvV : v ∉ V := (mem_sdiff.mp hv).2 have heW : e ∉ W := by intro he exact huV (mem_biUnion.mpr ⟨e, he, by simp [e]⟩) have hedis : ∀ b ∈ W, Disjoint e.val.toFinset b.val.toFinset := by intro b hb apply disjoint_left.mpr intro a ha hab have haV : a ∈ V := mem_biUnion.mpr ⟨b,hb,hab⟩ have hauv : a = u ∨ a = v := by simpa [e] using ha rcases hauv with rfl | rfl · exact huV haV · exact hvV haV have hnew : P (insert e W) := by constructor · intro a ha b hb hab rcases mem_insert.mp ha with rfl | ha <;> rcases mem_insert.mp hb with rfl | hb · exact (hab rfl).elim · exact hedis b hb · exact (hedis a ha).symm · exact hW.1 a ha b hb hab · intro a ha b hb hcolor rcases mem_insert.mp ha with rfl | ha <;> rcases mem_insert.mp hb with rfl | hb · rfl · exact (hno (mem_image.mpr ⟨b,hb,hcolor.symm⟩)).elim · exact (hno (mem_image.mpr ⟨a,ha,hcolor⟩)).elim · exact hW.2 ha hb hcolor have hle := hmax (insert e W) (mem_filter.mpr ⟨mem_univ _,hnew⟩) rw [card_insert_of_notMem heW] at hle omega
|U| is odd and |U| ≤ |W|.
Since n is odd and |U| + 2|W| = n, |U| must be odd. We then case split on whether |U| ≥ 3. If |U| ≥ 3, the helper lemma in338_odd_subset_colors applies to U and C to give |U| ≤ |C| = |W|. If |U| < 3, the oddness of |U| forces |U| = 1; since n ≥ 3 and 1 + 2|W| = n, we have |W| ≥ 1 ≥ |U|. Hence |U| ≤ |W| in all cases.
uses
in338_odd_subset_colorshave hUodd : U.card % 2 = 1 := by omega have hsmall : U.card ≤ W.card := by by_cases hU : 3 ≤ U.card · have hh := in338_odd_subset_colors c U C hU hUodd hcol omega · omega
W is a rainbow matching with n ≤ 3|W|.
We output W as the required matching. It satisfies the matching and rainbow conditions by definition. Combining n = |U| + 2|W| with |U| ≤ |W| yields n ≤ 3|W| via linear arithmetic, which establishes the theorem.
refine ⟨W, hW.1, hW.2, ?_⟩ omega
Fintype.equivOfCardEq- Two finite types with the same cardinality are equivalent (in bijection).
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
Sym2.inductionOn- Induction principle on unordered pairs, allowing one to assume the pair is of the form s(a, b).
SimpleGraph.Coloring.mk- Constructs a proper vertex coloring of a graph from a coloring function and a proof that adjacent vertices receive different colors.
congrArg- Applying a function to equal arguments produces equal results (x = y implies f(x) = f(y)).
SimpleGraph.recolorOfEquiv- Relabels the colors of a graph coloring along an equivalence of color types.
Fintype.equivFin- Every finite type α is equivalent to Fin (|α|).
Fintype.card_coe- The cardinality of a finite set viewed as a subtype equals its finset cardinality.
complete_graph_odd_line_graph_chromatic_number_eq- For an odd integer n ≥ 3, the chromatic number of the line graph of K_n (the chromatic index of K_n) is n.
card_biUnion- The cardinality of a union of pairwise disjoint finsets equals the sum of their cardinalities.
Sym2.card_toFinset_of_not_isDiag- An unordered pair with distinct endpoints has cardinality 2 when viewed as a finset.
sum_congr- Two finite sums over the same finset are equal if their summands agree on every element.
sum_const- The sum of a constant value b over a finset s equals |s| * b.
nsmul_eq_mul- Scalar multiplication by a natural number n equals ordinary multiplication by n.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
card_image_of_injOn- The image of a finset under an injective function has the same cardinality as the finset.
card_sdiff_add_card_eq_card- For any subset s ⊆ t of finsets, |t \ s| + |s| = |t|.
subset_univ- Every finset of elements of a finite type is a subset of the universal finset.
card_univ- The cardinality of the universal finset of a finite type α equals the cardinality of α.
Fintype.card_fin- The cardinality of Fin n is n.
wild_kn_mem- Any pair of distinct vertices u ≠ v in a complete graph forms an edge.
mem_univ- Every element of a finite type belongs to the universal finset.
card_insert_of_notMem- Inserting an element not already in a finset increases its cardinality by 1.
in338_odd_subset_colors- In a complete graph properly edge-colored by c, if an odd subset U of at least 3 vertices has all induced edges colored in C, then |U| ≤ |C|.
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 Finsetopen scoped Classical BigOperatorsset_option maxHeartbeats 4000000private theorem in338_odd_subset_colors {n k : ℕ} (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (U : Finset (Fin n)) (C : Finset (Fin k)) (hU : 3 ≤ U.card) (hodd : U.card % 2 = 1) (hcol : ∀ u ∈ U, ∀ v ∈ U, ∀ h : u ≠ v, c ⟨s(u,v),wild_kn_mem h⟩ ∈ C) : U.card ≤ C.card := by classical let E : Fin U.card ≃ ↥U := Fintype.equivOfCardEq (by simp) let f : Fin U.card ↪ Fin n := ⟨fun v => (E v).val, fun a b h => E.injective (Subtype.ext h)⟩ let cc := c.comap (SimpleGraph.Embedding.completeGraph f).toCopy.toLineGraphEmbedding.toHom have hcc : ∀ e : (⊤ : SimpleGraph (Fin U.card)).edgeSet, cc e ∈ C := by rintro ⟨e, he⟩ induction e using Sym2.inductionOn with | hf a b => have hab : a ≠ b := by simpa using he change c ⟨s(f a,f b),_⟩ ∈ C exact hcol (f a) (E a).property (f b) (E b).property (fun h => hab (f.injective h)) let cs : (⊤ : SimpleGraph (Fin U.card)).lineGraph.Coloring ↥C := SimpleGraph.Coloring.mk (fun e => ⟨cc e, hcc e⟩) (by intro a b hab heq exact (cc.valid hab) (congrArg Subtype.val heq)) have hcfin : (⊤ : SimpleGraph (Fin U.card)).lineGraph.Colorable C.card := by let cf := (SimpleGraph.recolorOfEquiv _ (Fintype.equivFin ↥C)) cs have : (⊤ : SimpleGraph (Fin U.card)).lineGraph.Colorable (Fintype.card ↥C) := ⟨cf⟩ simpa only [Fintype.card_coe] using this have hh := hcfin.chromaticNumber_le rw [complete_graph_odd_line_graph_chromatic_number_eq U.card hU hodd] at hh exact_mod_cast hhtheorem complete_graph_odd_rainbow_matching_third_bound {n k : ℕ} (hn : 3 ≤ n) (hodd : n % 2 = 1) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) : ∃ W : Finset (⊤ : SimpleGraph (Fin n)).edgeSet, (∀ a ∈ W, ∀ b ∈ W, a ≠ b → Disjoint a.val.toFinset b.val.toFinset) ∧ Set.InjOn (fun e => c e) (↑W : Set (⊤ : SimpleGraph (Fin n)).edgeSet) ∧ n ≤ 3 * W.card := by classical let E := (⊤ : SimpleGraph (Fin n)).edgeSet let P : Finset E → Prop := fun W => (∀ a ∈ W, ∀ b ∈ W, a ≠ b → Disjoint a.val.toFinset b.val.toFinset) ∧ Set.InjOn (fun e => c e) (↑W : Set E) let Q : Finset (Finset E) := univ.filter P have hQ : Q.Nonempty := ⟨∅, by simp [Q, P, Set.InjOn]⟩ obtain ⟨W, hWQ, hmax⟩ := Q.exists_max_image card hQ have hW : P W := (mem_filter.mp hWQ).2 let V : Finset (Fin n) := W.biUnion fun e => e.val.toFinset let U : Finset (Fin n) := univ \ V let C : Finset (Fin k) := W.image fun e => c e have hV : V.card = 2 * W.card := by dsimp only [V] rw [card_biUnion (by intro a ha b hb hab; exact hW.1 a ha b hb hab)] have htwo : ∀ e ∈ W, e.val.toFinset.card = 2 := by intro e _ exact Sym2.card_toFinset_of_not_isDiag e.val ((⊤ : SimpleGraph (Fin n)).not_isDiag_of_mem_edgeSet e.property) rw [sum_congr rfl htwo, sum_const, nsmul_eq_mul] simp only [Nat.cast_id, Nat.mul_comm] have hC : C.card = W.card := card_image_of_injOn hW.2 have hUV : U.card + V.card = n := by have hh := card_sdiff_add_card_eq_card (subset_univ V) simpa only [card_univ, Fintype.card_fin] using hh have hcol : ∀ u ∈ U, ∀ v ∈ U, ∀ h : u ≠ v, c ⟨s(u,v),wild_kn_mem h⟩ ∈ C := by intro u hu v hv huv by_contra hno let e : E := ⟨s(u,v),wild_kn_mem huv⟩ have huV : u ∉ V := (mem_sdiff.mp hu).2 have hvV : v ∉ V := (mem_sdiff.mp hv).2 have heW : e ∉ W := by intro he exact huV (mem_biUnion.mpr ⟨e, he, by simp [e]⟩) have hedis : ∀ b ∈ W, Disjoint e.val.toFinset b.val.toFinset := by intro b hb apply disjoint_left.mpr intro a ha hab have haV : a ∈ V := mem_biUnion.mpr ⟨b,hb,hab⟩ have hauv : a = u ∨ a = v := by simpa [e] using ha rcases hauv with rfl | rfl · exact huV haV · exact hvV haV have hnew : P (insert e W) := by constructor · intro a ha b hb hab rcases mem_insert.mp ha with rfl | ha <;> rcases mem_insert.mp hb with rfl | hb · exact (hab rfl).elim · exact hedis b hb · exact (hedis a ha).symm · exact hW.1 a ha b hb hab · intro a ha b hb hcolor rcases mem_insert.mp ha with rfl | ha <;> rcases mem_insert.mp hb with rfl | hb · rfl · exact (hno (mem_image.mpr ⟨b,hb,hcolor.symm⟩)).elim · exact (hno (mem_image.mpr ⟨a,ha,hcolor⟩)).elim · exact hW.2 ha hb hcolor have hle := hmax (insert e W) (mem_filter.mpr ⟨mem_univ _,hnew⟩) rw [card_insert_of_notMem heW] at hle omega have hUodd : U.card % 2 = 1 := by omega have hsmall : U.card ≤ W.card := by by_cases hU : 3 ≤ U.card · have hh := in338_odd_subset_colors c U C hU hUodd hcol omega · omega refine ⟨W, hW.1, hW.2, ?_⟩ omega