AFTD Auto-Formalizing Theoretical Domains

complete_graph_odd_rainbow_matching_third_bound

theoremverified

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

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⌉.

  1. 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.

    lines 11–29

    uses Fintype.equivOfCardEq, Subtype.ext, Sym2.inductionOn, SimpleGraph.Coloring.mk, congrArg, SimpleGraph.recolorOfEquiv, Fintype.equivFin, Fintype.card_coe

      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
  2. |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|.

    lines 30–32

    uses complete_graph_odd_line_graph_chromatic_number_eq

      have hh := hcfin.chromaticNumber_le
      rw [complete_graph_odd_line_graph_chromatic_number_eq U.card hU hodd] at hh
      exact_mod_cast hh
  3. 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|.

    lines 42–50

      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
  4. 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.

    lines 51–66

    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_fin

      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
  5. 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.

    lines 67–102

    uses wild_kn_mem, mem_univ, card_insert_of_notMem

      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
  6. |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.

    lines 103–108

    uses in338_odd_subset_colors

      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
  7. 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.

    lines 109–110

      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

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
See it in the graphDiscuss this resultChallenge it